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

DOI10.1007/978-3-642-45030-3_18zbMATH Open1329.05073arXiv1309.4713OpenAlexW2170766989MaRDI QIDQ2872083FDOQ2872083

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

Publication date: 14 January 2014

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

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.

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

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

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)

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)