<?xml version="1.0" encoding="utf-8"?>
<TEI xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:hal="http://hal.archives-ouvertes.fr/" xmlns:gml="http://www.opengis.net/gml/3.3/" xmlns:gmlce="http://www.opengis.net/gml/3.3/ce" version="1.1" xsi:schemaLocation="http://www.tei-c.org/ns/1.0 http://api.archives-ouvertes.fr/documents/aofr-sword.xsd">
  <teiHeader>
    <fileDesc>
      <titleStmt>
        <title>HAL TEI export of lirmm-00904537</title>
      </titleStmt>
      <publicationStmt>
        <distributor>CCSD</distributor>
        <availability status="restricted">
          <licence target="https://creativecommons.org/publicdomain/zero/1.0/">CC0 1.0 - Universal</licence>
        </availability>
        <date when="2026-05-03T08:51:19+02:00"/>
      </publicationStmt>
      <sourceDesc>
        <p part="N">HAL API Platform</p>
      </sourceDesc>
    </fileDesc>
  </teiHeader>
  <text>
    <body>
      <listBibl>
        <biblFull>
          <titleStmt>
            <title xml:lang="en">Bidimensionality of Geometric Intersection Graphs</title>
            <author role="aut">
              <persName>
                <forename type="first">Alexander</forename>
                <surname>Grigoriev</surname>
              </persName>
              <idno type="halauthorid">661190-0</idno>
              <affiliation ref="#struct-121919"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Athanassios</forename>
                <surname>Koutsonas</surname>
              </persName>
              <idno type="halauthorid">778368-0</idno>
              <affiliation ref="#struct-425861"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Dimitrios M.</forename>
                <surname>Thilikos</surname>
              </persName>
              <email type="md5">b12f47ffd4c78cdb273f5b91bb335a0e</email>
              <email type="domain">thilikos.Info</email>
              <idno type="idhal" notation="string">dimitrios-m-thilikos</idno>
              <idno type="idhal" notation="numeric">178742</idno>
              <idno type="halauthorid" notation="string">17649-178742</idno>
              <idno type="ORCID">https://orcid.org/0000-0003-0470-1800</idno>
              <idno type="IDREF">https://www.idref.fr/149337078</idno>
              <affiliation ref="#struct-388229"/>
              <affiliation ref="#struct-425861"/>
            </author>
            <editor role="depositor">
              <persName>
                <forename>Dimitrios</forename>
                <surname>Thilikos</surname>
              </persName>
              <email type="md5">b12f47ffd4c78cdb273f5b91bb335a0e</email>
              <email type="domain">thilikos.info</email>
            </editor>
          </titleStmt>
          <editionStmt>
            <edition n="v1" type="current">
              <date type="whenSubmitted">2013-11-14 16:16:36</date>
              <date type="whenWritten">2013-08-28</date>
              <date type="whenModified">2024-04-18 15:19:04</date>
              <date type="whenReleased">2013-11-29 15:45:44</date>
              <date type="whenProduced">2014-01-26</date>
              <ref type="externalLink" target="http://arxiv.org/pdf/1308.6166"/>
            </edition>
            <respStmt>
              <resp>contributor</resp>
              <name key="182048">
                <persName>
                  <forename>Dimitrios</forename>
                  <surname>Thilikos</surname>
                </persName>
                <email type="md5">b12f47ffd4c78cdb273f5b91bb335a0e</email>
                <email type="domain">thilikos.info</email>
              </name>
            </respStmt>
          </editionStmt>
          <publicationStmt>
            <distributor>CCSD</distributor>
            <idno type="halId">lirmm-00904537</idno>
            <idno type="halUri">https://hal-lirmm.ccsd.cnrs.fr/lirmm-00904537</idno>
            <idno type="halBibtex">grigoriev:lirmm-00904537</idno>
            <idno type="halRefHtml">&lt;i&gt;SOFSEM: Theory and Practice of Computer Science&lt;/i&gt;, Jan 2014, Špindlerův Mlýn, Czech Republic. pp.293-305, &lt;a target="_blank" href="https://dx.doi.org/10.1007/978-3-319-04298-5_26"&gt;&amp;#x27E8;10.1007/978-3-319-04298-5_26&amp;#x27E9;&lt;/a&gt;</idno>
            <idno type="halRef">SOFSEM: Theory and Practice of Computer Science, Jan 2014, Špindlerův Mlýn, Czech Republic. pp.293-305, &amp;#x27E8;10.1007/978-3-319-04298-5_26&amp;#x27E9;</idno>
            <availability status="restricted"/>
          </publicationStmt>
          <seriesStmt>
            <idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
            <idno type="stamp" n="ALGCO" corresp="LIRMM">Algorithmes, Graphes et Combinatoire</idno>
            <idno type="stamp" n="LIRMM">Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier</idno>
            <idno type="stamp" n="TDS-MACS">Réseau de recherche en Théorie des Systèmes Distribués, Modélisation, Analyse et Contrôle des Systèmes</idno>
            <idno type="stamp" n="MIPS">Mathématiques, Informatique, Physique et Systèmes</idno>
            <idno type="stamp" n="UNIV-MONTPELLIER">Université de Montpellier</idno>
            <idno type="stamp" n="UM-2015-2021" corresp="UNIV-MONTPELLIER">Université de Montpellier (2015-2021)</idno>
          </seriesStmt>
          <notesStmt>
            <note type="audience" n="2">International</note>
            <note type="invited" n="0">No</note>
            <note type="popular" n="0">No</note>
            <note type="peer" n="1">Yes</note>
            <note type="proceedings" n="1">Yes</note>
          </notesStmt>
          <sourceDesc>
            <biblStruct>
              <analytic>
                <title xml:lang="en">Bidimensionality of Geometric Intersection Graphs</title>
                <author role="aut">
                  <persName>
                    <forename type="first">Alexander</forename>
                    <surname>Grigoriev</surname>
                  </persName>
                  <idno type="halauthorid">661190-0</idno>
                  <affiliation ref="#struct-121919"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Athanassios</forename>
                    <surname>Koutsonas</surname>
                  </persName>
                  <idno type="halauthorid">778368-0</idno>
                  <affiliation ref="#struct-425861"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Dimitrios M.</forename>
                    <surname>Thilikos</surname>
                  </persName>
                  <email type="md5">b12f47ffd4c78cdb273f5b91bb335a0e</email>
                  <email type="domain">thilikos.Info</email>
                  <idno type="idhal" notation="string">dimitrios-m-thilikos</idno>
                  <idno type="idhal" notation="numeric">178742</idno>
                  <idno type="halauthorid" notation="string">17649-178742</idno>
                  <idno type="ORCID">https://orcid.org/0000-0003-0470-1800</idno>
                  <idno type="IDREF">https://www.idref.fr/149337078</idno>
                  <affiliation ref="#struct-388229"/>
                  <affiliation ref="#struct-425861"/>
                </author>
              </analytic>
              <monogr>
                <title level="m">40th International Conference on Current Trends in Theory and Practice of Computer Science</title>
                <meeting>
                  <title>SOFSEM: Theory and Practice of Computer Science</title>
                  <date type="start">2014-01-26</date>
                  <date type="end">2014-01-31</date>
                  <settlement>Špindlerův Mlýn</settlement>
                  <country key="CZ">Czech Republic</country>
                </meeting>
                <imprint>
                  <biblScope unit="volume">LNCS</biblScope>
                  <biblScope unit="issue">8327</biblScope>
                  <biblScope unit="pp">293-305</biblScope>
                  <date type="datePub">2014</date>
                </imprint>
              </monogr>
              <idno type="arxiv">1308.6166</idno>
              <idno type="doi">10.1007/978-3-319-04298-5_26</idno>
            </biblStruct>
          </sourceDesc>
          <profileDesc>
            <langUsage>
              <language ident="en">English</language>
            </langUsage>
            <textClass>
              <classCode scheme="halDomain" n="info.info-dm">Computer Science [cs]/Discrete Mathematics [cs.DM]</classCode>
              <classCode scheme="halDomain" n="math.math-co">Mathematics [math]/Combinatorics [math.CO]</classCode>
              <classCode scheme="halTypology" n="COMM">Conference papers</classCode>
              <classCode scheme="halOldTypology" n="COMM">Conference papers</classCode>
              <classCode scheme="halTreeTypology" n="COMM">Conference papers</classCode>
            </textClass>
            <abstract xml:lang="en">
              <p>Let B be a finite collection of geometric (not necessarily convex) bodies in the plane. Clearly, this class of geometric objects naturally generalizes the class of disks, lines, ellipsoids, and even convex polygons. We consider geometric intersection graphs GB where each body of the collection B is represented by a vertex, and two vertices of GB are adjacent if the intersection of the corresponding bodies is non-empty. For such graph classes and under natural restrictions on their maximum degree or subgraph exclusion, we prove that the relation between their treewidth and the maximum size of a grid minor is linear. These combinatorial results vastly extend the applicability of all the meta-algorithmic results of the bidimensionality theory to geometrically defined graph classes.</p>
            </abstract>
          </profileDesc>
        </biblFull>
      </listBibl>
    </body>
    <back>
      <listOrg type="structures">
        <org type="laboratory" xml:id="struct-121919" status="VALID">
          <orgName>Dept. Mathematics [Maastricht]</orgName>
          <desc>
            <address>
              <addrLine>Universiteit Maastricht, P.O. Box 616, 6200 MD Maastricht, The Netherlands</addrLine>
              <country key="NL"/>
            </address>
            <ref type="url">http://www.maastrichtuniversity.nl/web/Schools/DKE.htm</ref>
          </desc>
          <listRelation>
            <relation active="#struct-83832" type="direct"/>
          </listRelation>
        </org>
        <org type="department" xml:id="struct-425861" status="VALID">
          <orgName>Department of Mathematics [Athens]</orgName>
          <desc>
            <address>
              <addrLine>Panepistimioupolis, GR-157 84, Athens</addrLine>
              <country key="GR"/>
            </address>
            <ref type="url">http://noether.math.uoa.gr/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-502478" type="direct"/>
          </listRelation>
        </org>
        <org type="researchteam" xml:id="struct-388229" status="OLD">
          <orgName>Algorithmes, Graphes et Combinatoire</orgName>
          <orgName type="acronym">ALGCO</orgName>
          <date type="end">2021-12-31</date>
          <desc>
            <address>
              <addrLine>LIRMM, 161 rue Ada, 34000 Montpellier</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.lirmm.fr/equipes/ALGCO/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-181" type="direct"/>
            <relation name="UMR5506" active="#struct-410122" type="indirect"/>
            <relation name="UMR5506" active="#struct-441569" type="indirect"/>
          </listRelation>
        </org>
        <org type="institution" xml:id="struct-83832" status="VALID">
          <idno type="ROR">https://ror.org/02jz4aj89</idno>
          <orgName>Maastricht University [Maastricht]</orgName>
          <desc>
            <address>
              <addrLine>Universiteitssingel 40;6200 MD Maastricht</addrLine>
              <country key="NL"/>
            </address>
            <ref type="url">http://www.maastrichtuniversity.nl/</ref>
          </desc>
        </org>
        <org type="regroupinstitution" xml:id="struct-502478" status="VALID">
          <idno type="ROR">https://ror.org/04gnjpq42</idno>
          <orgName>National and Kapodistrian University of Athens</orgName>
          <orgName type="acronym">NKUA</orgName>
          <date type="start">1837-04-14</date>
          <desc>
            <address>
              <addrLine>Athens 157 72</addrLine>
              <country key="GR"/>
            </address>
            <ref type="url">https://en.uoa.gr/</ref>
          </desc>
        </org>
        <org type="laboratory" xml:id="struct-181" status="OLD">
          <idno type="IdRef">139590827</idno>
          <idno type="ISNI">0000000405990488</idno>
          <idno type="RNSR">199111950H</idno>
          <idno type="ROR">https://ror.org/013yean28</idno>
          <orgName>Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier</orgName>
          <orgName type="acronym">LIRMM</orgName>
          <date type="start">1995-01-01</date>
          <date type="end">2021-12-31</date>
          <desc>
            <address>
              <addrLine>161 rue Ada - 34095 Montpellier</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.lirmm.fr</ref>
          </desc>
          <listRelation>
            <relation name="UMR5506" active="#struct-410122" type="direct"/>
            <relation name="UMR5506" active="#struct-441569" type="direct"/>
          </listRelation>
        </org>
        <org type="institution" xml:id="struct-410122" status="OLD">
          <idno type="ISNI">0000000120970141</idno>
          <idno type="ROR">https://ror.org/051escj72</idno>
          <orgName>Université de Montpellier</orgName>
          <orgName type="acronym">UM</orgName>
          <date type="end">2021-12-31</date>
          <desc>
            <address>
              <addrLine>163 rue Auguste Broussonnet - 34090 Montpellier</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.umontpellier.fr/</ref>
          </desc>
        </org>
        <org type="regroupinstitution" xml:id="struct-441569" status="VALID">
          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <idno type="ROR">https://ror.org/02feahw73</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.cnrs.fr/</ref>
          </desc>
        </org>
      </listOrg>
    </back>
  </text>
</TEI>