Please use this identifier to cite or link to this item: http://hdl.handle.net/10525/384

 Title: On the Vertex Separation of Maximal Outerplanar Graphs Authors: Markov, Minko Keywords: Algorithmic Graph TheoryComputational ComplexityVertex SeparationLinear LayoutLayout StretchabiltyMaximal 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. URI: http://hdl.handle.net/10525/384 ISSN: 1312-6555 Appears in Collections: Volume 2 Number 3

Files in This Item:

File Description SizeFormat