Proper circular arc graphs as intersection graphs of paths on a grid

DOI10.1016/J.DAM.2019.02.010MaRDI QIDQ2416437zbMATH OpenOpenAlexWikidataFDO

Authors M. P. Mazzoleni, Bernard Ries, Esther Galby

Publication date 23 May 2019

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

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

zbMATH Keywords

intersection graphforbidden induced subgraphproper circular arc graph\(B_k\)-EPG graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph operations (line graphs, products, etc.) (05C76)

Abstract: In this paper we present a characterisation, by an infinite family of minimal forbidden induced subgraphs, of proper circular arc graphs which are intersection graphs of paths on a grid, where each path has at most one bend (turn).

Recommendations

• On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
• On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
• Partial Characterizations of Circular-Arc Graphs
• Partial characterizations of circular-arc graphs
• Some properties of edge intersection graphs of single bend paths on a grid

Cites work

• Characterizations of cographs as intersection graphs of paths on a grid
• Edge intersection graphs of single bend paths on a grid
• Edge-Intersection Graphs of k-Bend Paths in Grids
• Edge-intersection graphs of grid paths: the bend-number
• Graph theory
• Matrix characterizations of circular-arc graphs
• On edge intersection graphs of paths with 2 bends
• On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
• Proper Helly Circular-Arc Graphs
• Representation of a finite graph by a set of intervals on the real line
• Restricted circular-arc graphs and clique cycles
• Some properties of edge intersection graphs of single bend paths on a grid
• Some properties of edge intersection graphs of single-bend paths on a grid
• Structure theorems for some circular-arc graphs
• Topics in Intersection Graph Theory
• VPG and EPG bend-numbers of Halin graphs

Cited in

(6)

• scientific article; zbMATH DE number 1990726 (Why is no real title available?)
• Paths in interval graphs and circular arc graphs
• Contact Graphs of Circular Arcs
• Hyperideal-based intersection graphs
• Hardness and approximation for L-EPG and \(B_1\)-EPG graphs
• Characterizing path graphs by forbidden induced subgraphs

This page was built for publication: Proper circular arc graphs as intersection graphs of paths on a grid

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