Crossing-constrained hierarchical drawings

DOI10.1016/j.jda.2005.06.001zbMath1132.68506OpenAlexW1965325552MaRDI QIDQ2458930

Irene Finocchi

Publication date: 5 November 2007

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2005.06.001

zbMATH Keywords

NP-completenessGraph drawingCrossing minimizationHierarchical layout

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (1)

Two-layer drawings of bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• String graphs. II: Recognizing string graphs is NP-hard
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Edge crossings in drawings of bipartite graphs
• Drawing graphs in two layers
• Approximations for the maximum acyclic subgraph problem
• Graph drawing software
• Width-restricted layering of acyclic digraphs with consideration of dummy nodes
• Crossing Number is NP-Complete
• Noncrossing Subgraphs in Topological Layouts
• Efficient Planarity Testing
• Crossing Theory and Hierarchy Mapping
• Total Ordering Problem
• 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
• Decidability of string graphs
• Recognizing string graphs in NP

This page was built for publication: Crossing-constrained hierarchical drawings