<?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-03371693</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-07T17:19:02+02:00"/>
      </publicationStmt>
      <sourceDesc>
        <p part="N">HAL API Platform</p>
      </sourceDesc>
    </fileDesc>
  </teiHeader>
  <text>
    <body>
      <listBibl>
        <biblFull>
          <titleStmt>
            <title xml:lang="en">Complete Graph Drawings up to Triangle Mutations</title>
            <author role="aut">
              <persName>
                <forename type="first">Emeric</forename>
                <surname>Gioan</surname>
              </persName>
              <email type="md5">aa32d1c967f4089e573a57177ea1b5e1</email>
              <email type="domain">lirmm.fr</email>
              <idno type="idhal" notation="string">emeric-gioan</idno>
              <idno type="idhal" notation="numeric">740668</idno>
              <idno type="halauthorid" notation="string">28733-740668</idno>
              <idno type="ORCID">https://orcid.org/0009-0007-3370-5460</idno>
              <affiliation ref="#struct-1100628"/>
            </author>
            <editor role="depositor">
              <persName>
                <forename>Emeric</forename>
                <surname>Gioan</surname>
              </persName>
              <email type="md5">aa32d1c967f4089e573a57177ea1b5e1</email>
              <email type="domain">lirmm.fr</email>
            </editor>
            <funder>This research was part of the OMSMO Project (Oriented Matroids for Shape Modeling), supported by the Grant “Chercheurd’avenir 2015” (Région Occitanie, and Fonds Européen de Développement Régional FEDER).</funder>
          </titleStmt>
          <editionStmt>
            <edition n="v1" type="current">
              <date type="whenSubmitted">2021-10-08 18:44:53</date>
              <date type="whenModified">2025-12-02 03:18:10</date>
              <date type="whenReleased">2021-10-11 10:03:34</date>
              <date type="whenProduced">2022-06</date>
              <date type="whenEndEmbargoed">2021-10-08</date>
              <ref type="file" target="https://hal-lirmm.ccsd.cnrs.fr/lirmm-03371693v1/document">
                <date notBefore="2021-10-08"/>
              </ref>
              <ref type="file" subtype="author" n="1" target="https://hal-lirmm.ccsd.cnrs.fr/lirmm-03371693v1/file/Gioan%20-%20Complete%20graph%20drawings%20up%20to%20triangle%20mutations%20-%20SOURCE%20FOR%20DCG.pdf" id="file-3371693-2960316">
                <date notBefore="2021-10-08"/>
              </ref>
            </edition>
            <respStmt>
              <resp>contributor</resp>
              <name key="119041">
                <persName>
                  <forename>Emeric</forename>
                  <surname>Gioan</surname>
                </persName>
                <email type="md5">aa32d1c967f4089e573a57177ea1b5e1</email>
                <email type="domain">lirmm.fr</email>
              </name>
            </respStmt>
          </editionStmt>
          <publicationStmt>
            <distributor>CCSD</distributor>
            <idno type="halId">lirmm-03371693</idno>
            <idno type="halUri">https://hal-lirmm.ccsd.cnrs.fr/lirmm-03371693</idno>
            <idno type="halBibtex">gioan:lirmm-03371693</idno>
            <idno type="halRefHtml">&lt;i&gt;Discrete and Computational Geometry&lt;/i&gt;, 2022, 67, pp.985-1022. &lt;a target="_blank" href="https://dx.doi.org/10.1007/s00454-021-00339-8"&gt;&amp;#x27E8;10.1007/s00454-021-00339-8&amp;#x27E9;&lt;/a&gt;</idno>
            <idno type="halRef">Discrete and Computational Geometry, 2022, 67, pp.985-1022. &amp;#x27E8;10.1007/s00454-021-00339-8&amp;#x27E9;</idno>
            <availability status="restricted">
              <licence target="https://about.hal.science/hal-authorisation-v1/">HAL Authorization<ref corresp="#file-3371693-2960316"/></licence>
            </availability>
          </publicationStmt>
          <seriesStmt>
            <idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
            <idno type="stamp" n="UNIV-MONTP3">Université de Montpellier Paul-Valéry</idno>
            <idno type="stamp" n="UNIV-PERP">Université Perpignan Via Domitia</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="UNIV-MONTPELLIER">Université de Montpellier</idno>
            <idno type="stamp" n="UPVM-TI" corresp="UNIV-MONTP3">Publications UPVM texte intégral</idno>
            <idno type="stamp" n="UM-2015-2021" corresp="UNIV-MONTPELLIER">Université de Montpellier (2015-2021)</idno>
            <idno type="stamp" n="UM-EPE" corresp="UNIV-MONTPELLIER">Université de Montpellier - EPE</idno>
          </seriesStmt>
          <notesStmt>
            <note type="audience" n="2">International</note>
            <note type="popular" n="0">No</note>
            <note type="peer" n="1">Yes</note>
          </notesStmt>
          <sourceDesc>
            <biblStruct>
              <analytic>
                <title xml:lang="en">Complete Graph Drawings up to Triangle Mutations</title>
                <author role="aut">
                  <persName>
                    <forename type="first">Emeric</forename>
                    <surname>Gioan</surname>
                  </persName>
                  <email type="md5">aa32d1c967f4089e573a57177ea1b5e1</email>
                  <email type="domain">lirmm.fr</email>
                  <idno type="idhal" notation="string">emeric-gioan</idno>
                  <idno type="idhal" notation="numeric">740668</idno>
                  <idno type="halauthorid" notation="string">28733-740668</idno>
                  <idno type="ORCID">https://orcid.org/0009-0007-3370-5460</idno>
                  <affiliation ref="#struct-1100628"/>
                </author>
              </analytic>
              <monogr>
                <idno type="halJournalId" status="VALID">12620</idno>
                <idno type="issn">0179-5376</idno>
                <idno type="eissn">1432-0444</idno>
                <title level="j">Discrete and Computational Geometry</title>
                <imprint>
                  <publisher>Springer Verlag</publisher>
                  <biblScope unit="volume">67</biblScope>
                  <biblScope unit="pp">985-1022</biblScope>
                  <date type="datePub">2022-06</date>
                </imprint>
              </monogr>
              <idno type="doi">10.1007/s00454-021-00339-8</idno>
            </biblStruct>
          </sourceDesc>
          <profileDesc>
            <langUsage>
              <language ident="en">English</language>
            </langUsage>
            <textClass>
              <keywords scheme="author">
                <term xml:lang="en">Logical relations</term>
                <term xml:lang="en">Oriented matroid</term>
                <term xml:lang="en">Pseudoline arrangement</term>
                <term xml:lang="en">Algorithm</term>
                <term xml:lang="en">Triangle flip</term>
                <term xml:lang="en">Complete graph</term>
                <term xml:lang="en">Graph drawing</term>
              </keywords>
              <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="halDomain" n="info.info-cg">Computer Science [cs]/Computational Geometry [cs.CG]</classCode>
              <classCode scheme="halTypology" n="ART">Journal articles</classCode>
              <classCode scheme="halOldTypology" n="ART">Journal articles</classCode>
              <classCode scheme="halTreeTypology" n="ART">Journal articles</classCode>
            </textClass>
            <abstract xml:lang="en">
              <p>The main result of the paper can be stated in the following way: a complete graph drawing in the sphere, where two edges have at most one common point, which is either a crossing or a common endpoint, and no three edges share a crossing, is determined by the circular ordering of edges at each vertex, or equivalently by the set of pairs of edges that cross, up to homeomorphism and a sequence of triangle mutations. A triangle mutation (or switch, or flip) consists in passing an edge across the intersection of two other edges, assuming the three edges cross each other and the region delimited by the three edges has an empty intersection with the drawing. Equivalently, the result holds for a drawing in the plane assuming the drawing is given with a pair of edges indicating where the unbounded region is. The proof is constructive, based on an inductive algorithm that adds vertices and their incident edges one by one (actually yielding an extra property for the sequence of triangle mutations). This result generalizes Ringel's theorem on uniform pseudoline arrangements (or rank 3 uniform oriented matroids) to complete graph drawings. We also apply this result to plane projections (or visualizations) of a geometric spatial complete graph, in terms of the rank 4 uniform oriented matroid defined by its vertices. Independently, we prove that, for a complete graph drawing, the set of pairs of edges that cross determine, by first order logic formulas, the circular ordering of edges at each vertex, as well as further information.</p>
            </abstract>
          </profileDesc>
        </biblFull>
      </listBibl>
    </body>
    <back>
      <listOrg type="structures">
        <org type="researchteam" xml:id="struct-1100628" status="VALID">
          <orgName>Algorithmes, Graphes et Combinatoire</orgName>
          <orgName type="acronym">LIRMM | ALGCO</orgName>
          <date type="start">2022-01-01</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-1100620" type="direct"/>
            <relation active="#struct-101475" type="indirect"/>
            <relation active="#struct-300009" type="indirect"/>
            <relation name="UMR5506" active="#struct-441569" type="indirect"/>
            <relation name="UMR5506" active="#struct-1100589" type="indirect"/>
            <relation active="#struct-1219853" type="indirect"/>
          </listRelation>
        </org>
        <org type="laboratory" xml:id="struct-1100620" status="VALID">
          <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">2022-01-01</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 active="#struct-101475" type="direct"/>
            <relation active="#struct-300009" type="direct"/>
            <relation name="UMR5506" active="#struct-441569" type="direct"/>
            <relation name="UMR5506" active="#struct-1100589" type="direct"/>
            <relation active="#struct-1219853" type="direct"/>
          </listRelation>
        </org>
        <org type="institution" xml:id="struct-101475" status="VALID">
          <idno type="ROR">https://ror.org/03am2jy38</idno>
          <orgName>Université de Perpignan Via Domitia</orgName>
          <orgName type="acronym">UPVD</orgName>
          <desc>
            <address>
              <addrLine>52 avenue Paul Alduy - 66860 Perpignan Cedex 9</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.univ-perp.fr/</ref>
          </desc>
        </org>
        <org type="institution" xml:id="struct-300009" status="VALID">
          <idno type="ROR">https://ror.org/02kvxyf05</idno>
          <orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
          <orgName type="acronym">Inria</orgName>
          <desc>
            <address>
              <addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.inria.fr/en/</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>
        <org type="regroupinstitution" xml:id="struct-1100589" status="VALID">
          <idno type="ROR">https://ror.org/051escj72</idno>
          <orgName>Université de Montpellier</orgName>
          <orgName type="acronym">UM</orgName>
          <date type="start">2022-01-01</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-1219853" status="VALID">
          <idno type="IdRef">282217916</idno>
          <orgName>Université de Montpellier Paul-Valéry</orgName>
          <orgName type="acronym">UMPV</orgName>
          <date type="start">2025-01-01</date>
          <desc>
            <address>
              <addrLine>Université de Montpellier Paul-Valéry Route de Mende 34199 Montpellier Cedex 5</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.univ-montp3.fr/fr</ref>
          </desc>
        </org>
      </listOrg>
    </back>
  </text>
</TEI>