<?xml version="1.0" encoding="UTF-8"?>

<modsCollection xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://www.loc.gov/mods/v3" xsi:schemaLocation="http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-3.xsd">
<mods version="3.3">

<genre>conference paper</genre>

<titleInfo><title>Crossing minimization in perturbed drawings</title></titleInfo>

  
  
<titleInfo type="alternative">
  
  <title>LNCS</title>
</titleInfo>

<note type="publicationStatus">published</note>


<note type="qualityControlled">yes</note>

<name type="personal">
  <namePart type="given">Radoslav</namePart>
  <namePart type="family">Fulek</namePart>
  <role><roleTerm type="text">author</roleTerm> </role><identifier type="local">39F3FFE4-F248-11E8-B48F-1D18A9856A87</identifier><description xsi:type="identifierDefinition" type="orcid">0000-0001-8485-1774</description></name>
<name type="personal">
  <namePart type="given">Csaba D.</namePart>
  <namePart type="family">Tóth</namePart>
  <role><roleTerm type="text">author</roleTerm> </role></name>







<name type="corporate">
  <namePart></namePart>
  <identifier type="local">UlWa</identifier>
  <role>
    <roleTerm type="text">department</roleTerm>
  </role>
</name>



<name type="conference">
  <namePart>GD: Graph Drawing and Network Visualization</namePart>
</name>






<abstract lang="eng">Due to data compression or low resolution, nearby vertices and edges of a graph drawing may be bundled to a common node or arc. We model such a “compromised” drawing by a piecewise linear map φ:G → ℝ. We wish to perturb φ by an arbitrarily small ε&gt;0 into a proper drawing (in which the vertices are distinct points, any two edges intersect in finitely many points, and no three edges have a common interior point) that minimizes the number of crossings. An ε-perturbation, for every ε&gt;0, is given by a piecewise linear map (Formula Presented), where with ||·|| is the uniform norm (i.e., sup norm). We present a polynomial-time solution for this optimization problem when G is a cycle and the map φ has no spurs (i.e., no two adjacent edges are mapped to overlapping arcs). We also show that the problem becomes NP-complete (i) when G is an arbitrary graph and φ has no spurs, and (ii) when φ may have spurs and G is a cycle or a union of disjoint paths.</abstract>

<originInfo><publisher>Springer</publisher><dateIssued encoding="w3cdtf">2018</dateIssued><place><placeTerm type="text">Barcelona, Spain</placeTerm></place>
</originInfo>
<language><languageTerm authority="iso639-2b" type="code">eng</languageTerm>
</language>



<relatedItem type="host">
  <identifier type="isbn">9783030044138</identifier>
  <identifier type="arXiv">1808.07608</identifier>
  <identifier type="ISI">000672802500016</identifier><identifier type="doi">10.1007/978-3-030-04414-5_16</identifier>
<part><detail type="volume"><number>11282 </number></detail><extent unit="pages">229-241</extent>
</part>
</relatedItem>


<extension>
<bibliographicCitation>
<ista>Fulek R, Tóth CD. 2018. Crossing minimization in perturbed drawings. GD: Graph Drawing and Network Visualization, LNCS, vol. 11282, 229–241.</ista>
<short>R. Fulek, C.D. Tóth, in:, Springer, 2018, pp. 229–241.</short>
<mla>Fulek, Radoslav, and Csaba D. Tóth. &lt;i&gt;Crossing Minimization in Perturbed Drawings&lt;/i&gt;. Vol. 11282, Springer, 2018, pp. 229–41, doi:&lt;a href=&quot;https://doi.org/10.1007/978-3-030-04414-5_16&quot;&gt;10.1007/978-3-030-04414-5_16&lt;/a&gt;.</mla>
<chicago>Fulek, Radoslav, and Csaba D. Tóth. “Crossing Minimization in Perturbed Drawings,” 11282:229–41. Springer, 2018. &lt;a href=&quot;https://doi.org/10.1007/978-3-030-04414-5_16&quot;&gt;https://doi.org/10.1007/978-3-030-04414-5_16&lt;/a&gt;.</chicago>
<ama>Fulek R, Tóth CD. Crossing minimization in perturbed drawings. In: Vol 11282. Springer; 2018:229-241. doi:&lt;a href=&quot;https://doi.org/10.1007/978-3-030-04414-5_16&quot;&gt;10.1007/978-3-030-04414-5_16&lt;/a&gt;</ama>
<ieee>R. Fulek and C. D. Tóth, “Crossing minimization in perturbed drawings,” presented at the GD: Graph Drawing and Network Visualization, Barcelona, Spain, 2018, vol. 11282, pp. 229–241.</ieee>
<apa>Fulek, R., &amp;#38; Tóth, C. D. (2018). Crossing minimization in perturbed drawings (Vol. 11282, pp. 229–241). Presented at the GD: Graph Drawing and Network Visualization, Barcelona, Spain: Springer. &lt;a href=&quot;https://doi.org/10.1007/978-3-030-04414-5_16&quot;&gt;https://doi.org/10.1007/978-3-030-04414-5_16&lt;/a&gt;</apa>
</bibliographicCitation>
</extension>
<recordInfo><recordIdentifier>5791</recordIdentifier><recordCreationDate encoding="w3cdtf">2018-12-30T22:59:15Z</recordCreationDate><recordChangeDate encoding="w3cdtf">2025-07-10T11:53:00Z</recordChangeDate>
</recordInfo>
</mods>
</modsCollection>
