Inserting Multiple Edges into a Planar Graph

DOI10.7155/jgaa.00631zbMath1530.05132OpenAlexW2262426677MaRDI QIDQ6075710

Markus Chimani, Petr Hliněný

Publication date: 20 September 2023

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00631

zbMATH Keywords

fixed-parameter algorithmcrossing number of the graphmultiple edge insertion problem

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• On shortest disjoint paths in planar graphs
• Crossing number and weighted crossing number of near-planar graphs
• On the complexity of embedding planar graphs to minimize certain distance measures
• Vertex insertion approximates the crossing number of apex graphs
• A framework for solving VLSI graph layout problems
• The crossing number of a projective graph is quadratic in the face-width
• Computing minimum length paths of a given homotopy class
• Inserting an edge into a planar graph
• Computing crossing numbers in quadratic time
• Hardness of approximation for crossing number
• The graph crossing number and its variants: a survey
• Crossing number for graphs with bounded pathwidth
• A tighter insertion-based approximation of the crossing number
• Star-struck by fixed embeddings: modern crossing number heuristics
• Exact crossing number parameterized by vertex cover
• Toroidal grid minors and stretch in embedded graphs
• Undirected single-source shortest paths with positive integer weights in linear time
• Shortest vertex-disjoint two-face paths in planar graphs
• Crossing Number is NP-Complete
• Euclidean shortest paths in the presence of rectilinear barriers
• On the Crossing Number of Almost Planar Graphs
• Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
• On-Line Planarity Testing
• Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
• An algorithm for the graph crossing number problem
• Faster shortest-path algorithms for planar graphs
• Advances in the Planarization Method: Effective Multiple Edge Insertions
• A subpolynomial approximation algorithm for graph crossing number in low-degree graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Inserting Multiple Edges into a Planar Graph