Noncrossing Subgraphs in Topological Layouts
From MaRDI portal
Publication:3357538
DOI10.1137/0404022zbMath0731.68047OpenAlexW2081580682MaRDI QIDQ3357538
Jaroslav Nešetřil, Jan Kratochvíl, Anna Lubiw
Publication date: 1991
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0404022
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10)
Related Items (25)
Bad drawings of small complete graphs ⋮ Complete graph drawings up to triangle mutations ⋮ The complexity of induced minors and related problems ⋮ Advances on Testing C-Planarity of Embedded Flat Clustered Graphs ⋮ Unnamed Item ⋮ Parameterized analysis and crossing minimization problems ⋮ Configurations with few crossings in topological graphs ⋮ On the complexity of trial and error for constraint satisfaction problems ⋮ Simple realizability of complete abstract topological graphs simplified ⋮ The Complexity of Drawing Graphs on Few Lines and Few Planes ⋮ Topological Drawings of Complete Bipartite Graphs ⋮ Make a graph singly connected by edge orientations ⋮ Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs ⋮ Simple realizability of complete abstract topological graphs in P ⋮ Crossing-constrained hierarchical drawings ⋮ On the planar split thickness of graphs ⋮ An algorithm for the maximum weight independent set problem on outerstring graphs ⋮ The Complexity of Several Realizability Problems for Abstract Topological Graphs ⋮ Polyline drawings with topological constraints ⋮ Connecting the dots (with minimum crossings) ⋮ Planar 3-SAT with a clause/variable cycle ⋮ Advancements on SEFE and partitioned book embedding problems ⋮ Plane subgraphs in geometric complement of 2-factor and complete bipartite geometric graph ⋮ The complexity of detecting crossingfree configurations in the plane ⋮ Satisfiability of co-nested formulas
This page was built for publication: Noncrossing Subgraphs in Topological Layouts
