Graphs with large obstacle numbers

DOI10.1007/978-3-642-16926-7_27MaRDI QIDQ3057633zbMATH OpenOpenAlexFDO

Authors Padmini Mukkamala, János Pach, Deniz Sarıöz

Publication date 16 November 2010

Published in Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-16926-7_27

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

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

Cites work

• A combinatorial distinction between the Euclidean and projective planes
• Arrangements of segments that share endpoints: Single face results
• Blocking visibility for points in general position
• Coloring a Family of Circular Arcs
• Erdős-Hajnal-type results on intersection patterns of geometric objects
• Excluding Induced Subgraphs III: A General Asymptotic
• Excluding induced subgraphs: quadrilaterals
• Excluding induced subgraphs. II: Extremal graphs
• Extremal problems in discrete geometry
• scientific article; zbMATH DE number 431988 (Why is no real title available?)
• scientific article; zbMATH DE number 1054787 (Why is no real title available?)
• scientific article; zbMATH DE number 2058507 (Why is no real title available?)
• 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?)
• Obstacle numbers of graphs
• Ramsey-type theorems
• Some remarks on the theory of graphs
• Split Graphs Having Dilworth Number Two
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The number of polytopes, configurations and real matroids
• Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
• Visibility Algorithms in the Plane

Cited in

(12)

• On obstacle numbers
• Grid obstacle representation of graphs
• Convex obstacle numbers of outerplanar graphs and bipartite permutation graphs
• Obstructing visibilities with one obstacle
• Lower bounds on the obstacle number of graphs
• Obstacle numbers of planar graphs
• Graphs with obstacle number greater than one
• Mutual witness Gabriel drawings of complete bipartite graphs
• Mutual witness Gabriel drawings of complete bipartite graphs
• Bounding and computing obstacle numbers of graphs
• On the structure of graphs with low obstacle number
• Obstacle numbers of graphs

This page was built for publication: Graphs with large obstacle numbers

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