Inserting an edge into a planar graph
From MaRDI portal
Publication:1774149
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
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