Orthogonal graph drawing with inflexible edges

DOI10.1007/978-3-319-18173-8_4zbMATH Open1460.68072arXiv1404.2943OpenAlexW1682423028MaRDI QIDQ2947010FDOQ2947010

Authors: Thomas Bläsius, Ignaz Rutter, Sebastian B. C. Lehmann 

Publication date: 21 September 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We consider the problem of creating plane orthogonal drawings of 4-planar graphs (planar graphs with maximum degree 4) with constraints on the number of bends per edge. More precisely, we have a flexibility function assigning to each edge $e$ a natural number $mathrmflex(e)$, its flexibility. The problem FlexDraw asks whether there exists an orthogonal drawing such that each edge $e$ has at most $mathrmflex(e)$ bends. It is known that FlexDraw is NP-hard if $mathrmflex(e)=0$ for every edge $e$. On the other hand, FlexDraw can be solved efficiently if $mathrmflex(e)ge1$ and is trivial if $mathrmflex(e)ge2$ for every edge $e$. To close the gap between the NP-hardness for $mathrmflex(e)=0$ and the efficient algorithm for $mathrmflex(e)ge1$, we investigate the computational complexity of FlexDraw in case only few edges are inflexible (i.e., have flexibility~$0$). We show that for any $varepsilon>0$ FlexDraw is NP-complete for instances with $O(n^{v}arepsilon)$ inflexible edges with pairwise distance $Omega(n^{1-varepsilon})$ (including the case where they induce a matching). On the other hand, we give an FPT-algorithm with running time $O(2^{k}cdotncdot{T}_{mathrmflow}(n))$, where $T_{mathrmflow}(n)$ is the time necessary to compute a maximum flow in a planar flow network with multiple sources and sinks, and $k$ is the number of inflexible edges having at least one endpoint of degree 4.

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

Recommendations

• Orthogonal graph drawing with inflexible edges
• Orthogonal graph drawing with flexibility constraints
• Orthogonal graph drawing with flexibility constraints
• Optimal orthogonal graph drawing with convex bend costs
• Optimal Orthogonal Graph Drawing with Convex Bend Costs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Flows in graphs (05C21)

Cites Work

• A better heuristic for orthogonal graph drawings
• Orthogonal graph drawing with inflexible edges
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• Orthogonal graph drawing with flexibility constraints
• On the computational complexity of upward and rectilinear planarity testing
• On-line maintenance of triconnected components with SPQR-trees
• Spirality and Optimal Orthogonal Drawings
• Optimal Orthogonal Graph Drawing with Convex Bend Costs
• Accelerated bend minimization

Cited In (11)

• Interactive orthogonal graph drawing
• Orthogonal layout with optimal face complexity
• Optimal orthogonal graph drawing with convex bend costs
• Relating bends and size in orthogonal graph drawings
• Orthogonal graph drawing with flexibility constraints
• Orthogonal graph drawing with flexibility constraints
• Orthogonal graph drawing with inflexible edges
• Orthogonal graph drawing with inflexible edges
• Orthogonal layout with optimal face complexity
• Orthogonal-ordering constraints are tough
• Orthogonal Drawings of Plane Graphs Without Bends

This page was built for publication: Orthogonal graph drawing with inflexible edges

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