Recognizing Outer 1-Planar Graphs in Linear Time

Autor:	Kathrin Hanauer, Franz J. Brandenburg, Josef Reislhuber, Andreas Gleiβner, Christian Bachmaier, Daniel Neuwirth, Christopher Auer
Rok vydání:	2013
Předmět:	Combinatorics Discrete mathematics Indifference graph symbols.namesake Book embedding Pathwidth Chordal graph Outerplanar graph Partial k-tree symbols 1-planar graph Mathematics Planar graph
Zdroj:	Graph Drawing ISBN: 9783319038407 Graph Drawing
DOI:	10.1007/978-3-319-03841-4_10
Popis:	A graph is outer 1-planar o1p if it can be drawn in the plane such that all vertices are on the outer face and each edge is crossed at most once. o1p graphs generalize outerplanar graphs, which can be recognized in linear time and specialize 1-planar graphs, whose recognition is $\mathcal{NP}$ -hard. Our main result is a linear-time algorithm that first tests whether a graphi¾?G is o1p, and then computes an embedding. Moreover, the algorithm can augment G to a maximal o1p graph. If G is not o1p, then it includes one of six minors see Fig. 3, which are also detected by the recognition algorithm. Hence, the algorithm returns a positive or negative witness for o1p.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::ff94336fb03f6c3ed650517e5062ae86 https://doi.org/10.1007/978-3-319-03841-4_10 Zobrazit plný text záznamu