Geodesic
On the Vertex Separation of Maximal Outerplanar Graphs
Serdica Journal of Computing, Tome 2 (2008) no. 3, pp. 207-238

Voir la notice de l'article provenant de la source Bulgarian Digital Mathematics Library

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.
Keywords: Algorithmic Graph Theory, Computational Complexity, Vertex Separation, Linear Layout, Layout Stretchabilty, Maximal Outerplanar Graph 
@article{SJC_2008_2_3_a0,
     author = {Markov, Minko},
     title = {On the {Vertex} {Separation} of {Maximal} {Outerplanar} {Graphs}},
     journal = {Serdica Journal of Computing},
     pages = {207--238},
     publisher = {mathdoc},
     volume = {2},
     number = {3},
     year = {2008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SJC_2008_2_3_a0/}
}
TY  - JOUR
AU  - Markov, Minko
TI  - On the Vertex Separation of Maximal Outerplanar Graphs
JO  - Serdica Journal of Computing
PY  - 2008
SP  - 207
EP  - 238
VL  - 2
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJC_2008_2_3_a0/
LA  - en
ID  - SJC_2008_2_3_a0
ER  - 
%0 Journal Article
%A Markov, Minko
%T On the Vertex Separation of Maximal Outerplanar Graphs
%J Serdica Journal of Computing
%D 2008
%P 207-238
%V 2
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJC_2008_2_3_a0/
%G en
%F SJC_2008_2_3_a0
Markov, Minko. On the Vertex Separation of Maximal Outerplanar Graphs. Serdica Journal of Computing, Tome 2 (2008) no. 3, pp. 207-238. http://geodesic.mathdoc.fr/item/SJC_2008_2_3_a0/