Edge intersection graphs of systems of paths on a grid with a bounded number of bends

DOI10.1016/j.dam.2009.06.015zbMath1227.05200OpenAlexW2064314629MaRDI QIDQ967371

Andrei Asinowski, Andrew Suk

Publication date: 28 April 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2009.06.015

zbMATH Keywords

edge intersection graphsgrid paths

Mathematics Subject Classification ID

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

Related Items (16)

On edge intersection graphs of paths with 2 bends ⋮ Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid ⋮ Graphs of edge-intersecting and non-splitting paths ⋮ Edge-Intersection Graphs of k-Bend Paths in Grids ⋮ Hardness and approximation for L-EPG and \(B_1\)-EPG graphs ⋮ Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs ⋮ Edge-intersection graphs of boundary-generated paths in a grid ⋮ On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid ⋮ Edge-intersection graphs of grid paths: the bend-number ⋮ Unnamed Item ⋮ On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid ⋮ EPG-representations with Small Grid-Size ⋮ Some properties of edge intersection graphs of single-bend paths on a grid ⋮ On the bend-number of planar and outerplanar graphs ⋮ On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid ⋮ Characterizations of cographs as intersection graphs of paths on a grid

Cites Work

• Unnamed Item
• Unnamed Item
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Representing edge intersection graphs of paths on degree 4 trees
• Edge intersection graphs of single bend paths on a grid
• A proof of Alon’s second eigenvalue conjecture and related problems
• Better expanders and superconcentrators
• Edge-Intersection Graphs of k-Bend Paths in Grids
• Lower Bounds for Approximation by Nonlinear Manifolds
• On the Betti Numbers of Real Varieties

This page was built for publication: Edge intersection graphs of systems of paths on a grid with a bounded number of bends