# On the Vertex Separation of Maximal Outerplanar Graphs

Serdica Journal of Computing (2008)

- Volume: 2, Issue: 3, page 207-238
- ISSN: 1312-6555

## Access Full Article

top## Abstract

top## How to cite

topMarkov, Minko. "On the Vertex Separation of Maximal Outerplanar Graphs." Serdica Journal of Computing 2.3 (2008): 207-238. <http://eudml.org/doc/11463>.

@article{Markov2008,

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.},

author = {Markov, Minko},

journal = {Serdica Journal of Computing},

keywords = {Algorithmic Graph Theory; Computational Complexity; Vertex Separation; Linear Layout; Layout Stretchabilty; Maximal Outerplanar Graph; algorithmic graph theory; computational complexity; vertex separation; linear layout; layout stretchabilty; maximal outerplanar graph},

language = {eng},

number = {3},

pages = {207-238},

publisher = {Institute of Mathematics and Informatics Bulgarian Academy of Sciences},

title = {On the Vertex Separation of Maximal Outerplanar Graphs},

url = {http://eudml.org/doc/11463},

volume = {2},

year = {2008},

}

TY - JOUR

AU - Markov, Minko

TI - On the Vertex Separation of Maximal Outerplanar Graphs

JO - Serdica Journal of Computing

PY - 2008

PB - Institute of Mathematics and Informatics Bulgarian Academy of Sciences

VL - 2

IS - 3

SP - 207

EP - 238

AB - 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.

LA - eng

KW - Algorithmic Graph Theory; Computational Complexity; Vertex Separation; Linear Layout; Layout Stretchabilty; Maximal Outerplanar Graph; algorithmic graph theory; computational complexity; vertex separation; linear layout; layout stretchabilty; maximal outerplanar graph

UR - http://eudml.org/doc/11463

ER -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.