Drawing planar graphs with a prescribed inner face

DOI10.1007/978-3-319-03841-4_28MaRDI QIDQ2867668zbMATH OpenOpenAlexFDO

Authors Tamara Mchedlidze, Martin Nöllenburg, Ignaz Rutter

Publication date 20 December 2013

Published in Graph Drawing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Given a plane graph $G$ (i.e., a planar graph with a fixed planar embedding) and a simple cycle $C$ in $G$ whose vertices are mapped to a convex polygon, we consider the question whether this drawing can be extended to a planar straight-line drawing of $G$. We characterize when this is possible in terms of simple necessary conditions, which we prove to be sufficient. This also leads to a linear-time testing algorithm. If a drawing extension exists, it can be computed in the same running time.

Recommendations

• Extending convex partial drawings of graphs
• Drawing graphs in the plane with a prescribed outer face and polynomial area
• Drawing graphs in the plane with a prescribed outer face and polynomial area
• Graph Drawing
• On embedding a cycle in a plane graph

Cited in

(9)

• The complexity of drawing a graph in a polygonal region
• Extending convex partial drawings of graphs
• Drawing planar graphs with prescribed face areas
• scientific article; zbMATH DE number 841998 (Why is no real title available?)
• Drawing graphs in the plane with a prescribed outer face and polynomial area
• Drawing graphs in the plane with a prescribed outer face and polynomial area
• Drawing Simultaneously Embedded Graphs with Few Bends
• Harborth's conjecture for 4-regular planar graphs
• Drawing planar graphs

This page was built for publication: Drawing planar graphs with a prescribed inner face

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