Extending partial 1-planar drawings

DOI10.4230/LIPICS.ICALP.2020.43MaRDI QIDQ6842533zbMATH OpenFDO

Authors Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute, Martin Nöllenburg

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.43

zbMATH Keywords

1-planarityextension problemsparameterized algorithms

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• Acyclic coloring of IC-planar graphs
• Adding one edge to planar graphs makes crossing number and 1-planarity hard
• Algorithms for graphs embeddable with few crossings per edge
• An annotated bibliography on 1-planarity
• Chromatic number, independence ratio, and crossing number
• Computing crossing numbers in quadratic time
• Contact representations of planar graphs: extending a partial representation is hard
• Convex drawings of graphs with non-convex boundary constraints
• Drawing graphs in the plane with a prescribed outer face and polynomial area
• Drawing partially embedded and simultaneously planar graphs
• Ein Sechsfarbenproblem auf der Kugel
• Extending convex partial drawings of graphs
• Extending partial representations of circle graphs
• Extending partial representations of function graphs and permutation graphs
• Extending partial representations of interval graphs
• Extending partial representations of proper and unit interval graphs
• Extending partial representations of subclasses of chordal graphs
• Extending simple drawings
• Extending upward planar graph drawings
• Fundamentals of parameterized complexity
• Graph minors. III. Planar tree-width
• L-visibility drawings of IC-planar graphs
• Minimal obstructions for 1-immersions and hardness of 1-planarity testing
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• Parameterized algorithms
• Partial and Constrained Level Planarity
• Recognizing and drawing IC-planar graphs
• Recognizing IC-planar and NIC-planar graphs
• Testing Planarity of Partially Embedded Graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The partial visibility representation extension problem

Cited in

(9)

• On k-plane insertion into plane drawings
• The parameterized complexity of extending stack layouts
• Crossing-optimal extension of simple drawings
• The peculiarities of extending queue layouts
• The complexity of extending fair allocations of indivisible goods
• OOPS: optimized one-planarity solver via SAT
• The parameterized complexity of extending stack layouts
• OOPS: optimized one-planarity solver via SAT
• Structural parameterizations of simultaneous planarity

This page was built for publication: Extending partial 1-planar drawings

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