On the Vertex Separation of Maximal Outerplanar Graphs

Markov, 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 -