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

Algorithms for the Hypergraph and the Minor Crossing Number Problems, Inserting an edge into a geometric embedding, Advances in the Planarization Method: Effective Multiple Edge Insertions, 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, 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