On the Vertex Separation of Maximal Outerplanar Graphs

Authors

  • Minko Markov

DOI:

https://doi.org/10.55630/sjc.2008.2.207-238

Keywords:

Algorithmic Graph Theory, Computational Complexity, Vertex Separation, Linear Layout, Layout Stretchabilty, Maximal Outerplanar Graph

Abstract

We investigate the NP-complete problem Vertex Separation (VS) on Maximal Outerplanar Graphs (mops). We formulate and prove a “main theorem for mops”, a necessary and sufficient condition for the vertex separation of a mop being k. The main theorem reduces the vertex separation of mops to a special kind of stretchability, one that we call affixability, of submops.

Downloads

Published

2008-12-02

Issue

Section

Articles