Inserting an edge into a planar graph

DOI10.1007/s00453-004-1128-8zbMath1065.68075OpenAlexW3136685299WikidataQ56977320 ScholiaQ56977320MaRDI QIDQ1774149

Petra Mutzel, Carsten Gutwenger, René Weiskircher

Publication date: 29 April 2005

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-004-1128-8

zbMATH Keywords

crossingsgraph drawing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (29)

Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics ⋮ Straight-Line Drawability of a Planar Graph Plus an Edge ⋮ Star-struck by fixed embeddings: modern crossing number heuristics ⋮ Inserting Multiple Edges into a Planar Graph ⋮ Planar tanglegram layouts and single edge insertion ⋮ Characterizing planar tanglegram layouts and applications to edge insertion problems ⋮ How to Draw a Planarization ⋮ Extending simple drawings ⋮ Unnamed Item ⋮ Algorithms for the Hypergraph and the Minor Crossing Number Problems ⋮ A New Approach to Exact Crossing Minimization ⋮ Vertex insertion approximates the crossing number of apex graphs ⋮ A branch-and-cut approach to the crossing number problem ⋮ How to Draw a Planarization ⋮ Crossing number and weighted crossing number of near-planar graphs ⋮ Unnamed Item ⋮ A tighter insertion-based approximation of the crossing number ⋮ Inserting an edge into a geometric embedding ⋮ Inserting an edge into a geometric embedding ⋮ Toroidal grid minors and stretch in embedded graphs ⋮ Crossing and Weighted Crossing Number of Near-Planar Graphs ⋮ Approximating the Crossing Number of Apex Graphs ⋮ Non-planar core reduction of graphs ⋮ Inserting one edge into a simple drawing is hard ⋮ Advances in the Planarization Method: Effective Multiple Edge Insertions ⋮ The Crossing Number of Graphs: Theory and Computation ⋮ Simultaneous Embedding ⋮ An effective crossing minimisation heuristic based on star insertion ⋮ 1-planarity testing and embedding: an experimental study

This page was built for publication: Inserting an edge into a planar graph