On the structure of graphs with low obstacle number

DOI10.1007/S00373-011-1027-0MaRDI QIDQ659699zbMATH OpenOpenAlexFDO

Authors János Pach, Deniz Sarıöz

Publication date 24 January 2012

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00373-011-1027-0

zbMATH Keywords

enumerationsplit graphsforbidden induced subgraphsvisibility graphobstacle numberpolygonal obstacleshereditary graph property

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 1424310 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• scientific article; zbMATH DE number 970795 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• Excluding Induced Subgraphs III: A General Asymptotic
• Excluding induced subgraphs. II: Extremal graphs
• Excluding induced subgraphs: quadrilaterals
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• Visibility Algorithms in the Plane

Cited in

(17)

• Geodesic obstacle representation of graphs
• On obstacle numbers
• Obstructing visibilities with one obstacle
• Obstacle numbers of graphs
• Lower bounds on the obstacle number of graphs
• A Remark on Elastic Graphs with the Symmetric Cone Obstacle
• Mutual witness Gabriel drawings of complete bipartite graphs
• Grid obstacle representation of graphs
• A characterization of biconnected graphs reachable by robots jumping over \(m\) obstacles
• Mutual witness Gabriel drawings of complete bipartite graphs
• Graphs with large obstacle numbers
• Convex obstacle numbers of outerplanar graphs and bipartite permutation graphs
• Outside-obstacle representations with all vertices on the outer face
• Graphs with obstacle number greater than one
• Obstacle numbers of planar graphs
• On reachability in graphs with obstacles
• Geodesic obstacle representation of graphs

This page was built for publication: On the structure of graphs with low obstacle number

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