Algorithmic Graph Theory Computational Complexity Vertex Separation Linear Layout Layout Stretchabilty Maximal Outerplanar Graph
Issue Date:
2008
Publisher:
Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Citation:
Serdica Journal of Computing, Vol. 2, No 3, (2008), 207p-238p
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.
