<oai_dc:dc xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ http://www.openarchives.org/OAI/2.0/oai_dc.xsd">
  <dc:creator>Alcón, Liliana</dc:creator>
  <dc:creator>Bonomo, Flavia</dc:creator>
  <dc:creator>Durán, Guillermo</dc:creator>
  <dc:creator>Gutierrez, Marisa</dc:creator>
  <dc:creator>Mazzoleni, María Pía</dc:creator>
  <dc:creator>Ries, Bernard</dc:creator>
  <dc:creator>Valencia-Pabon, Mario</dc:creator>
  <dc:date>2018</dc:date>
  <dc:description xmlns:ns0="xml" ns0:lang="en">Golumbic, Lipshteyn and Stern [12] proved that every graph can be represented as  the edge intersection graph of paths on a grid (EPG graph), i.e., one can associate  with each vertex of the graph a nontrivial path on a rectangular grid such that two  vertices are adjacent if and only if the corresponding paths share at least one edge of  the grid. For a nonnegative integer k, Bk-EPG graphs are defined as EPG graphs  admitting a model in which each path has at most k bends. Circular-arc graphs are  intersection graphs of open arcs of a circle. It is easy to see that every circular-arc  graph is a B4-EPG graph, by embedding the circle into a rectangle of the grid. In this  paper, we prove that circular-arc graphs are B3-EPG, and that there exist circular-arc  graphs which are not B2-EPG. If we restrict ourselves to rectangular representations  (i.e., the union of the paths used in the model is contained in the boundary of a  rectangle of the grid), we obtain EPR (edge intersection of paths in a rectangle)  representations. We may define Bk-EPR graphs, k ≥ 0, the same way as Bk- EPG  graphs. Circular-arc graphs are clearly B4-EPR graphs and we will show that there  exist circular-arc graphs that are not B3-EPR graphs. We also show that normal  circulararc graphs are B2-EPR graphs and that there exist normal circular-arc graphs  that are not B1-EPR graphs. Finally, we characterize B1-EPR graphs by a family of  minimal forbidden induced subgraphs, and show that they form a subclass of normal  Helly circular-arc graphs.</dc:description>
  <dc:format>application/pdf</dc:format>
  <dc:identifier>https://folia.unifr.ch/global/documents/307803</dc:identifier>
  <dc:identifier>https://folia.unifr.ch/documents/307803/files/epg2_rero.pdf</dc:identifier>
  <dc:language>eng</dc:language>
  <dc:relation>info:eu-repo/semantics/altIdentifier/doi/10.1016/j.dam.2016.08.004</dc:relation>
  <dc:rights>info:eu-repo/semantics/openAccess</dc:rights>
  <dc:rights>License undefined</dc:rights>
  <dc:source>Discrete applied mathematics. - 2018, vol. 234, p. 12-21</dc:source>
  <dc:subject xmlns:ns1="xml" ns1:lang="en">Edge intersection graphs</dc:subject>
  <dc:subject xmlns:ns2="xml" ns2:lang="en">paths on a grid</dc:subject>
  <dc:subject xmlns:ns3="xml" ns3:lang="en">forbidden induced subgraphs</dc:subject>
  <dc:subject xmlns:ns4="xml" ns4:lang="en">(normal, Helly) circular-arc graphs</dc:subject>
  <dc:subject xmlns:ns5="xml" ns5:lang="en">powers of cycles</dc:subject>
  <dc:subject>info:eu-repo/classification/udc/33</dc:subject>
  <dc:title xmlns:ns6="xml" ns6:lang="en">On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid</dc:title>
  <dc:type>http://purl.org/coar/resource_type/c_6501</dc:type>
</oai_dc:dc>
