Drawing graphs using a small number of obstacles

DOI10.1007/s00454-017-9919-2zbMath1380.05135arXiv1610.04741OpenAlexW2749402853MaRDI QIDQ1702349

Pavel Valtr, Josef Cibulka, Martin Balko

Publication date: 28 February 2018

Published in: Lecture Notes in Computer Science, Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

obstacle numbergeometric drawingarrangements of line segmentsobstacle representationarrangement of line segments

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Related Items (8)

Grid obstacle representation of graphs ⋮ Mutual witness Gabriel drawings of complete bipartite graphs ⋮ Mutual witness Gabriel drawings of complete bipartite graphs ⋮ Obstructing Visibilities with One Obstacle ⋮ Unnamed Item ⋮ Outside-obstacle representations with all vertices on the outer face ⋮ Drawing graphs using a small number of obstacles ⋮ Geodesic obstacle representation of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds on the obstacle number of graphs
• On the structure of graphs with low obstacle number
• Obstacle numbers of graphs
• On the maximal number of edges of many faces in an arrangement
• Planar realizations of nonlinear Davenport-Schinzel sequences by segments
• Convex independent sets and 7-holes in restricted planar point sets
• The number of edges of many faces in a line segment arrangement
• Graphs drawn with few crossings per edge
• Drawing graphs using a small number of obstacles
• Arrangements of segments that share endpoints: Single face results
• On obstacle numbers
• Convex Obstacle Numbers of Outerplanar Graphs and Bipartite Permutation Graphs
• Obstructing Visibilities with One Obstacle
• Graphs with Large Obstacle Numbers
• Graphs with Obstacle Number Greater than One

This page was built for publication: Drawing graphs using a small number of obstacles