Inserting Multiple Edges into a Planar Graph

DOI10.7155/JGAA.00631MaRDI QIDQ6075710zbMATH OpenOpenAlexFDO

Authors Markus Chimani, Petr Hliněný

Publication date 20 September 2023

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

crossing number of the graphfixed-parameter algorithmmultiple 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)

Recommendations

• Inserting multiple edges into a planar graph
• Inserting an edge into a geometric embedding
• Inserting an edge into a geometric embedding
• Inserting a vertex into a planar graph
• Inserting an edge into a planar graph
• Inserting an edge into a planar graph
• Approximating the crossing number of graphs embeddable in any orientable surface
• Crossing number, pair-crossing number, and expansion

Cites work

• A framework for solving VLSI graph layout problems
• A subpolynomial approximation algorithm for graph crossing number in low-degree graphs
• Adding one edge to planar graphs makes crossing number and 1-planarity hard
• Advances in the planarization method: effective multiple edge insertions
• An algorithm for the graph crossing number problem
• Approximating the crossing number of graphs embeddable in any orientable surface
• Computing crossing numbers in quadratic time
• Computing minimum length paths of a given homotopy class
• Crossing number and weighted crossing number of near-planar graphs
• Crossing number for graphs with bounded pathwidth
• Crossing Number is NP-Complete
• Euclidean shortest paths in the presence of rectilinear barriers
• Exact crossing number parameterized by vertex cover
• Faster shortest-path algorithms for planar graphs
• Hardness of approximation for crossing number
• scientific article; zbMATH DE number 5485473 (Why is no real title available?)
• scientific article; zbMATH DE number 2080088 (Why is no real title available?)
• scientific article; zbMATH DE number 1500682 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
• Inserting a vertex into a planar graph
• Inserting an edge into a planar graph
• On graph crossing number and edge planarization
• On shortest disjoint paths in planar graphs
• On the complexity of embedding planar graphs to minimize certain distance measures
• On the Crossing Number of Almost Planar Graphs
• On-Line Planarity Testing
• Shortest vertex-disjoint two-face paths in planar graphs
• Star-struck by fixed embeddings: modern crossing number heuristics
• The crossing number of a projective graph is quadratic in the face-width
• The graph crossing number and its variants: a survey
• Toroidal grid minors and stretch in embedded graphs
• Undirected single-source shortest paths with positive integer weights in linear time
• Vertex insertion approximates the crossing number of apex graphs

Cited in

(2)

• Inserting an edge into a geometric embedding
• On k-plane insertion into plane drawings

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6075710)