Obstacle numbers of graphs

DOI10.1007/S00454-009-9233-8MaRDI QIDQ977184zbMATH OpenOpenAlexFDO

Authors Hannah Alpert, Christina L. Koch, Joshua D. Laison

Publication date 21 June 2010

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00454-009-9233-8

zbMATH Keywords

interval bigraphvisibility graphobstacle numbercircular arc graphconvex obstacle numbernon-double-covering circular arc graphproper circular arc graph

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Graphs with large obstacle numbers
• Lower bounds on the obstacle number of graphs
• On the structure of graphs with low obstacle number

Cites work

• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 139795 (Why is no real title available?)
• scientific article; zbMATH DE number 1933220 (Why is no real title available?)
• scientific article; zbMATH DE number 1990673 (Why is no real title available?)
• scientific article; zbMATH DE number 1743762 (Why is no real title available?)
• scientific article; zbMATH DE number 1786502 (Why is no real title available?)
• scientific article; zbMATH DE number 2170335 (Why is no real title available?)
• scientific article; zbMATH DE number 5019923 (Why is no real title available?)
• Algorithmic graph theory and perfect graphs
• Characterizing circular-arc graphs
• Circular-arc graphs with clique cover number two
• Interval bigraphs and circular arc graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Linear-time recognition of circular-arc graphs
• Matrix characterizations of circular-arc graphs
• Polynomial time recognition of unit circular-arc graphs
• Research Problems in Discrete Geometry
• Small Ramsey numbers
• The Erdos-Szekeres problem on points in convex position – a survey
• Topics in Intersection Graph Theory
• Two remarks on circular arc graphs

Cited in

(17)

• Geodesic obstacle representation of graphs
• On obstacle numbers
• Obstructing visibilities with one obstacle
• Crossing edge minimization in radial outerplanar layered graphs using segment paths
• Mutual witness Gabriel drawings of complete bipartite graphs
• Grid obstacle representation of graphs
• A characterization of 2-tree proper interval 3-graphs
• Mutual witness Gabriel drawings of complete bipartite graphs
• Graphs with large obstacle numbers
• Convex obstacle numbers of outerplanar graphs and bipartite permutation graphs
• Bounding and computing obstacle numbers of graphs
• Outside-obstacle representations with all vertices on the outer face
• Grid-obstacle representations with connections to staircase guarding
• On reachability in graphs with obstacles
• Obstructions to a general characterization of graph correspondences
• Geodesic obstacle representation of graphs
• The Robot Crawler Number of a Graph

This page was built for publication: Obstacle numbers of graphs

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