2-layer right angle crossing drawings

DOI10.1007/S00453-012-9706-7zbMath1303.05129OpenAlexW2054401820WikidataQ62042385 ScholiaQ62042385MaRDI QIDQ476445

Peter Eades, Walter Didimo, Emilio Di Giacomo, Giuseppe Liotta

Publication date: 2 December 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9706-7

zbMATH Keywords

graph drawingNP-hardnessefficient algorithmsright angle crossings2-layer drawingstesting algorithms

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (17)

Recognizing and drawing IC-planar graphs ⋮ On RAC drawings of 1-planar graphs ⋮ The Stub Resolution of 1-planar Graphs ⋮ Unnamed Item ⋮ 2-Layer Graph Drawings with Bounded Pathwidth ⋮ 1-fan-bundle-planar drawings of graphs ⋮ A heuristic approach towards drawings of graphs with high crossing resolution ⋮ Drawing graphs with right angle crossings ⋮ On RAC drawings of graphs with one bend per edge ⋮ On RAC drawings of graphs with one bend per edge ⋮ Quantum graph drawing (best student paper) ⋮ Fixed-parameter algorithms for computing RAC drawings of graphs ⋮ Fixed-parameter algorithms for computing bend-restricted RAC drawings of graphs ⋮ Beyond Planar Graphs: Introduction ⋮ Right Angle Crossing Drawings of Graphs ⋮ 2-Layer k-Planar Graphs ⋮ Fan-planarity: properties and complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graphs that admit right angle crossing drawings
• Area, curve complexity, and crossing resolution of non-planar graph drawings
• Drawing graphs with right angle crossings
• A characterization of complete bipartite RAC graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A branch and bound algorithm for minimizing the number of crossing arcs in bipartite graphs
• Edge crossings in drawings of bipartite graphs
• Drawing graphs in two layers
• A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation
• A fixed-parameter approach to 2-layer planarization
• An Alternative Method to Crossing Minimization on Hierarchical Graphs
• The Crossing-Angle Resolution in Graph Drawing
• Heuristics for the Maximum 2-layer RAC Subgraph Problem
• On the Size of Graphs That Admit Polyline Drawings with Few Bends and Crossing Angles
• The Quality Ratio of RAC Drawings and Planar Drawings of Planar Graphs
• The Straight-Line RAC Drawing Problem Is NP-Hard
• 2-Layer Right Angle Crossing Drawings
• Drawing Graphs with Right Angle Crossings
• Right Angle Crossing Graphs and 1-Planarity
• 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
• Graph Drawing and Applications for Software and Knowledge Engineers
• Notes on large angle crossing graphs
• On the Perspectives Opened by Right Angle Crossing Drawings

This page was built for publication: 2-layer right angle crossing drawings