SEFE with no mapping via large induced outerplane graphs in plane graphs

DOI10.1007/978-3-642-45030-3_18MaRDI QIDQ2872083zbMATH OpenOpenAlexFDO

Authors Patrizio Angelini, Fabrizio Frati, Joachim Gudmundsson, W. Evans

Publication date 14 January 2014

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.4713

zbMATH Keywords

simultaneous embedding with no mapping and with fixed edges

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: We show that every $n$-vertex planar graph admits a simultaneous embedding with no mapping and with fixed edges with any $(n/2)$-vertex planar graph. In order to achieve this result, we prove that every $n$-vertex plane graph has an induced outerplane subgraph containing at least $n/2$ vertices. Also, we show that every $n$-vertex planar graph and every $n$-vertex planar partial 3-tree admit a simultaneous embedding with no mapping and with fixed edges.

Recommendations

• SEFE without mapping via large induced outerplane graphs in plane graphs
• Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges
• Characterizations of Restricted Pairs of Planar Graphs Allowing Simultaneous Embedding with Fixed Edges
• Characterizing simultaneous embedding with fixed edges
• Simultaneous embedding of embedded planar graphs

Cited in

(1)

• SEFE without mapping via large induced outerplane graphs in plane graphs

This page was built for publication: SEFE with no mapping via large induced outerplane graphs in plane graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2872083)