scientific article; zbMATH DE number 7559402

DOI10.4230/LIPICS.MFCS.2020.31MaRDI QIDQ5089197zbMATH OpenFDO

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

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/2007.05346

zbMATH Keywords

\(1\)-planarityextension problems

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• 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
• 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
• Embedding planar graphs at fixed vertex locations
• 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 subclasses of chordal graphs
• Extending simple drawings
• Fundamentals of parameterized complexity
• Graphs drawn with few crossings per edge
• How to draw a planar graph on a grid
• scientific article; zbMATH DE number 432759 (Why is no real title available?)
• Kernelization using structural parameters on sparse graph classes
• L-visibility drawings of IC-planar graphs
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• Parameterized algorithms
• Partial and Constrained Level Planarity
• 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

Cited in

(10)

• Parameterized analysis and crossing minimization problems
• Inserting one edge into a simple drawing is hard
• Planarizing graphs and their drawings by vertex splitting
• Fixed-parameter algorithms for computing RAC drawings of graphs
• Fixed-parameter algorithms for computing bend-restricted RAC drawings of graphs
• On k-plane insertion into plane drawings
• The parameterized complexity of extending stack layouts
• The peculiarities of extending queue layouts
• The parameterized complexity of extending stack layouts
• Structural parameterizations of \(k\)-planarity

This page was built for publication:

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