Inserting an edge into a planar graph

DOI10.1007/s00453-004-1128-8zbMath1065.68075WikidataQ56977320 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

crossings; graph drawing

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C10: Planar graphs; geometric and topological aspects of graph theory

Related Items

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