UnivTrevesV1, Istex, Corpus, bibRecord, 001143

The complexity of detecting crossingfree configurations in the plane

Identifieur interne : 001143 ( Istex/Corpus ); précédent : 001142; suivant : 001144

The complexity of detecting crossingfree configurations in the plane

Auteurs : Klaus Jansen ; Gerhard J. Woeginger

Source :

BIT Numerical Mathematics [ 0006-3835 ] ; 1993-12-01.

RBID : ISTEX:6597678048C75955853DD52F707557F26EC2DF5D

Abstract

Abstract: The computational complexity of the following type of problem is studied. Given a geometric graphG=(P, S) whereP is a set of points in the Euclidean plane andS a set of straight (closed) line segments between pairs of points inP, we want to know whetherG possesses a crossingfree subgraph of a special type. We analyze the problem of detecting crossingfree spanning trees, one factors and two factors in the plane. We also consider special restrictions on the slopes and on the lengths of the edges in the subgraphs.

Url:

https://api.istex.fr/document/6597678048C75955853DD52F707557F26EC2DF5D/fulltext/pdf

DOI: 10.1007/BF01990536

Links to Exploration step

ISTEX:6597678048C75955853DD52F707557F26EC2DF5D

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">The complexity of detecting crossingfree configurations in the plane</title>
<author><name sortKey="Jansen, Klaus" sort="Jansen, Klaus" uniqKey="Jansen K" first="Klaus" last="Jansen">Klaus Jansen</name>
<affiliation><mods:affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, W-5500, Trier, Germany</mods:affiliation>
</affiliation>
<affiliation><mods:affiliation>Institut für Informationsverarbeitung, Technische Universität Graz, Klosterwiesgasse 32/II, A-8010, Graz, Austria</mods:affiliation>
</affiliation>
</author>
<author><name sortKey="Woeginger, Gerhard J" sort="Woeginger, Gerhard J" uniqKey="Woeginger G" first="Gerhard J." last="Woeginger">Gerhard J. Woeginger</name>
<affiliation><mods:affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, W-5500, Trier, Germany</mods:affiliation>
</affiliation>
<affiliation><mods:affiliation>Institut für Informationsverarbeitung, Technische Universität Graz, Klosterwiesgasse 32/II, A-8010, Graz, Austria</mods:affiliation>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:6597678048C75955853DD52F707557F26EC2DF5D</idno>
<date when="1993" year="1993">1993</date>
<idno type="doi">10.1007/BF01990536</idno>
<idno type="url">https://api.istex.fr/document/6597678048C75955853DD52F707557F26EC2DF5D/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001143</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001143</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">The complexity of detecting crossingfree configurations in the plane</title>
<author><name sortKey="Jansen, Klaus" sort="Jansen, Klaus" uniqKey="Jansen K" first="Klaus" last="Jansen">Klaus Jansen</name>
<affiliation><mods:affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, W-5500, Trier, Germany</mods:affiliation>
</affiliation>
<affiliation><mods:affiliation>Institut für Informationsverarbeitung, Technische Universität Graz, Klosterwiesgasse 32/II, A-8010, Graz, Austria</mods:affiliation>
</affiliation>
</author>
<author><name sortKey="Woeginger, Gerhard J" sort="Woeginger, Gerhard J" uniqKey="Woeginger G" first="Gerhard J." last="Woeginger">Gerhard J. Woeginger</name>
<affiliation><mods:affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, W-5500, Trier, Germany</mods:affiliation>
</affiliation>
<affiliation><mods:affiliation>Institut für Informationsverarbeitung, Technische Universität Graz, Klosterwiesgasse 32/II, A-8010, Graz, Austria</mods:affiliation>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="j">BIT Numerical Mathematics</title>
<title level="j" type="abbrev">BIT</title>
<idno type="ISSN">0006-3835</idno>
<idno type="eISSN">1572-9125</idno>
<imprint><publisher>Kluwer Academic Publishers</publisher>
<pubPlace>Dordrecht</pubPlace>
<date type="published" when="1993-12-01">1993-12-01</date>
<biblScope unit="volume">33</biblScope>
<biblScope unit="issue">4</biblScope>
<biblScope unit="page" from="580">580</biblScope>
<biblScope unit="page" to="595">595</biblScope>
</imprint>
<idno type="ISSN">0006-3835</idno>
</series>
<idno type="istex">6597678048C75955853DD52F707557F26EC2DF5D</idno>
<idno type="DOI">10.1007/BF01990536</idno>
<idno type="ArticleID">BF01990536</idno>
<idno type="ArticleID">Art4</idno>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0006-3835</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: The computational complexity of the following type of problem is studied. Given a geometric graphG=(P, S) whereP is a set of points in the Euclidean plane andS a set of straight (closed) line segments between pairs of points inP, we want to know whetherG possesses a crossingfree subgraph of a special type. We analyze the problem of detecting crossingfree spanning trees, one factors and two factors in the plane. We also consider special restrictions on the slopes and on the lengths of the edges in the subgraphs.</div>
</front>
</TEI>
<istex><corpusName>springer</corpusName>
<author><json:item><name>Klaus Jansen</name>
<affiliations><json:string>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, W-5500, Trier, Germany</json:string>
<json:string>Institut für Informationsverarbeitung, Technische Universität Graz, Klosterwiesgasse 32/II, A-8010, Graz, Austria</json:string>
</affiliations>
</json:item>
<json:item><name>Gerhard J. Woeginger</name>
<affiliations><json:string>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, W-5500, Trier, Germany</json:string>
<json:string>Institut für Informationsverarbeitung, Technische Universität Graz, Klosterwiesgasse 32/II, A-8010, Graz, Austria</json:string>
</affiliations>
</json:item>
</author>
<articleId><json:string>BF01990536</json:string>
<json:string>Art4</json:string>
</articleId>
<language><json:string>eng</json:string>
</language>
<originalGenre><json:string>OriginalPaper</json:string>
</originalGenre>
<abstract>Abstract: The computational complexity of the following type of problem is studied. Given a geometric graphG=(P, S) whereP is a set of points in the Euclidean plane andS a set of straight (closed) line segments between pairs of points inP, we want to know whetherG possesses a crossingfree subgraph of a special type. We analyze the problem of detecting crossingfree spanning trees, one factors and two factors in the plane. We also consider special restrictions on the slopes and on the lengths of the edges in the subgraphs.</abstract>
<qualityIndicators><score>6.056</score>
<pdfVersion>1.3</pdfVersion>
<pdfPageSize>450 x 684 pts</pdfPageSize>
<refBibsNative>false</refBibsNative>
<keywordCount>0</keywordCount>
<abstractCharCount>526</abstractCharCount>
<pdfWordCount>5166</pdfWordCount>
<pdfCharCount>25617</pdfCharCount>
<pdfPageCount>16</pdfPageCount>
<abstractWordCount>88</abstractWordCount>
</qualityIndicators>
<title>The complexity of detecting crossingfree configurations in the plane</title>
<refBibs><json:item><author><json:item><name>M,R Garey</name>
</json:item>
<json:item><name>D,S Johnson</name>
</json:item>
</author>
<host><author></author>
<title>Computers and Intractability</title>
<publicationDate>1979</publicationDate>
</host>
<publicationDate>1979</publicationDate>
</json:item>
<json:item><author><json:item><name>J Kratochv~l</name>
</json:item>
<json:item><name>A Lubiw</name>
</json:item>
<json:item><name>J Ne~etfil</name>
</json:item>
</author>
<host><volume>4</volume>
<pages><last>244</last>
<first>223</first>
</pages>
<author></author>
<title>SIAM J. Disc. Math</title>
<publicationDate>1991</publicationDate>
</host>
<title>Nonerossing subgraphs in topological layouts</title>
<publicationDate>1991</publicationDate>
</json:item>
<json:item><host><author><json:item><name>T Lengauer</name>
</json:item>
</author>
<title>Combinatorial Algorithm,s for Integrated Circuit Layout</title>
<publicationDate>1990</publicationDate>
</host>
</json:item>
<json:item><host><author><json:item><name>F Rendl</name>
</json:item>
<json:item><name>G~,J </name>
</json:item>
</author>
<title>W~eginger~ Re~nstructing sets ~f ~rth~onal line segments in the plane~ t~ appear in Discr</title>
</host>
</json:item>
<json:item><author><json:item><name>P Rosenstiehl</name>
</json:item>
<json:item><name>R,E Tarjan</name>
</json:item>
</author>
<host><volume>1</volume>
<pages><last>353</last>
<first>343</first>
</pages>
<author></author>
<title>Discr. Comp. Geometry</title>
<publicationDate>1986</publicationDate>
</host>
<title>Rectilinear planar layout of planar graphs and bipolar orientations</title>
<publicationDate>1986</publicationDate>
</json:item>
<json:item><author><json:item><name>P,J Slater</name>
</json:item>
<json:item><name>E,J Cockayne</name>
</json:item>
<json:item><name>S,T </name>
</json:item>
<json:item><name>Hedetniemi </name>
</json:item>
</author>
<host><volume>10</volume>
<pages><last>701</last>
<first>692</first>
</pages>
<author></author>
<title>SIAM J. Comput</title>
<publicationDate>1981</publicationDate>
</host>
<title>Information dissemination in trees</title>
<publicationDate>1981</publicationDate>
</json:item>
<json:item><author><json:item><name>G Toussaint</name>
</json:item>
</author>
<host><pages><last>1347</last>
<first>1324</first>
</pages>
<author></author>
<title>Proc. 5th International Conference on Pattern Recognition</title>
<publicationDate>1980</publicationDate>
</host>
<title>Pattern recognition and geometrical complexity</title>
<publicationDate>1980</publicationDate>
</json:item>
</refBibs>
<genre><json:string>research-article</json:string>
</genre>
<host><volume>33</volume>
<pages><last>595</last>
<first>580</first>
</pages>
<issn><json:string>0006-3835</json:string>
</issn>
<issue>4</issue>
<subject><json:item><value>Numeric Computing</value>
</json:item>
<json:item><value>Mathematics, general</value>
</json:item>
<json:item><value>Computational Mathematics and Numerical Analysis</value>
</json:item>
</subject>
<journalId><json:string>10543</json:string>
</journalId>
<genre><json:string>journal</json:string>
</genre>
<language><json:string>unknown</json:string>
</language>
<eissn><json:string>1572-9125</json:string>
</eissn>
<title>BIT Numerical Mathematics</title>
<publicationDate>1993</publicationDate>
<copyrightDate>1993</copyrightDate>
</host>
<categories><wos><json:string>science</json:string>
<json:string>mathematics, applied</json:string>
<json:string>computer science, software engineering</json:string>
</wos>
<scienceMetrix><json:string>natural sciences</json:string>
<json:string>mathematics & statistics</json:string>
<json:string>numerical & computational mathematics</json:string>
</scienceMetrix>
</categories>
<publicationDate>1993</publicationDate>
<copyrightDate>1993</copyrightDate>
<doi><json:string>10.1007/BF01990536</json:string>
</doi>
<id>6597678048C75955853DD52F707557F26EC2DF5D</id>
<score>0.4424935</score>
<fulltext><json:item><extension>pdf</extension>
<original>true</original>
<mimetype>application/pdf</mimetype>
<uri>https://api.istex.fr/document/6597678048C75955853DD52F707557F26EC2DF5D/fulltext/pdf</uri>
</json:item>
<json:item><extension>zip</extension>
<original>false</original>
<mimetype>application/zip</mimetype>
<uri>https://api.istex.fr/document/6597678048C75955853DD52F707557F26EC2DF5D/fulltext/zip</uri>
</json:item>
<istex:fulltextTEI uri="https://api.istex.fr/document/6597678048C75955853DD52F707557F26EC2DF5D/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">The complexity of detecting crossingfree configurations in the plane</title>
<respStmt><resp>Références bibliographiques récupérées via GROBID</resp>
<name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name>
</respStmt>
<respStmt><resp>Références bibliographiques récupérées via GROBID</resp>
<name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name>
</respStmt>
</titleStmt>
<publicationStmt><authority>ISTEX</authority>
<publisher>Kluwer Academic Publishers</publisher>
<pubPlace>Dordrecht</pubPlace>
<availability><p>the BIT Foundation, 1993</p>
</availability>
<date>1992-11-15</date>
</publicationStmt>
<notesStmt><note>Part I Computer Science</note>
</notesStmt>
<sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">The complexity of detecting crossingfree configurations in the plane</title>
<author xml:id="author-1"><persName><forename type="first">Klaus</forename>
<surname>Jansen</surname>
</persName>
<affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, W-5500, Trier, Germany</affiliation>
<affiliation>Institut für Informationsverarbeitung, Technische Universität Graz, Klosterwiesgasse 32/II, A-8010, Graz, Austria</affiliation>
</author>
<author xml:id="author-2"><persName><forename type="first">Gerhard</forename>
<surname>Woeginger</surname>
</persName>
<affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, W-5500, Trier, Germany</affiliation>
<affiliation>Institut für Informationsverarbeitung, Technische Universität Graz, Klosterwiesgasse 32/II, A-8010, Graz, Austria</affiliation>
</author>
</analytic>
<monogr><title level="j">BIT Numerical Mathematics</title>
<title level="j" type="abbrev">BIT</title>
<idno type="journal-ID">10543</idno>
<idno type="pISSN">0006-3835</idno>
<idno type="eISSN">1572-9125</idno>
<idno type="issue-article-count">14</idno>
<idno type="volume-issue-count">4</idno>
<imprint><publisher>Kluwer Academic Publishers</publisher>
<pubPlace>Dordrecht</pubPlace>
<date type="published" when="1993-12-01"></date>
<biblScope unit="volume">33</biblScope>
<biblScope unit="issue">4</biblScope>
<biblScope unit="page" from="580">580</biblScope>
<biblScope unit="page" to="595">595</biblScope>
</imprint>
</monogr>
<idno type="istex">6597678048C75955853DD52F707557F26EC2DF5D</idno>
<idno type="DOI">10.1007/BF01990536</idno>
<idno type="ArticleID">BF01990536</idno>
<idno type="ArticleID">Art4</idno>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><creation><date>1992-11-15</date>
</creation>
<langUsage><language ident="en">en</language>
</langUsage>
<abstract xml:lang="en"><p>Abstract: The computational complexity of the following type of problem is studied. Given a geometric graphG=(P, S) whereP is a set of points in the Euclidean plane andS a set of straight (closed) line segments between pairs of points inP, we want to know whetherG possesses a crossingfree subgraph of a special type. We analyze the problem of detecting crossingfree spanning trees, one factors and two factors in the plane. We also consider special restrictions on the slopes and on the lengths of the edges in the subgraphs.</p>
</abstract>
<textClass><keywords scheme="Journal Subject"><list><head>Mathematics</head>
<item><term>Numeric Computing</term>
</item>
<item><term>Mathematics, general</term>
</item>
<item><term>Computational Mathematics and Numerical Analysis</term>
</item>
</list>
</keywords>
</textClass>
</profileDesc>
<revisionDesc><change when="1992-11-15">Created</change>
<change when="1993-12-01">Published</change>
<change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-11-22">References added</change>
<change xml:id="refBibs-istex" who="#ISTEX-API" when="2017-01-20">References added</change>
</revisionDesc>
</teiHeader>
</istex:fulltextTEI>
<json:item><extension>txt</extension>
<original>false</original>
<mimetype>text/plain</mimetype>
<uri>https://api.istex.fr/document/6597678048C75955853DD52F707557F26EC2DF5D/fulltext/txt</uri>
</json:item>
</fulltext>
<metadata><istex:metadataXml wicri:clean="Springer, Publisher found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration>
<istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType>
<istex:document><Publisher><PublisherInfo><PublisherName>Kluwer Academic Publishers</PublisherName>
<PublisherLocation>Dordrecht</PublisherLocation>
</PublisherInfo>
<Journal><JournalInfo JournalProductType="ArchiveJournal" NumberingStyle="Unnumbered"><JournalID>10543</JournalID>
<JournalPrintISSN>0006-3835</JournalPrintISSN>
<JournalElectronicISSN>1572-9125</JournalElectronicISSN>
<JournalTitle>BIT Numerical Mathematics</JournalTitle>
<JournalAbbreviatedTitle>BIT</JournalAbbreviatedTitle>
<JournalSubjectGroup><JournalSubject Type="Primary">Mathematics</JournalSubject>
<JournalSubject Type="Secondary">Numeric Computing</JournalSubject>
<JournalSubject Type="Secondary">Mathematics, general</JournalSubject>
<JournalSubject Type="Secondary">Computational Mathematics and Numerical Analysis</JournalSubject>
</JournalSubjectGroup>
</JournalInfo>
<Volume><VolumeInfo VolumeType="Regular" TocLevels="0"><VolumeIDStart>33</VolumeIDStart>
<VolumeIDEnd>33</VolumeIDEnd>
<VolumeIssueCount>4</VolumeIssueCount>
</VolumeInfo>
<Issue IssueType="Regular"><IssueInfo TocLevels="0"><IssueIDStart>4</IssueIDStart>
<IssueIDEnd>4</IssueIDEnd>
<IssueArticleCount>14</IssueArticleCount>
<IssueHistory><CoverDate><DateString>1993</DateString>
<Year>1993</Year>
<Month>12</Month>
</CoverDate>
</IssueHistory>
<IssueCopyright><CopyrightHolderName>BIT Foundation</CopyrightHolderName>
<CopyrightYear>1993</CopyrightYear>
</IssueCopyright>
</IssueInfo>
<Article ID="Art4"><ArticleInfo Language="En" ArticleType="OriginalPaper" NumberingStyle="Unnumbered" TocLevels="0" ContainsESM="No"><ArticleID>BF01990536</ArticleID>
<ArticleDOI>10.1007/BF01990536</ArticleDOI>
<ArticleSequenceNumber>4</ArticleSequenceNumber>
<ArticleTitle Language="En">The complexity of detecting crossingfree configurations in the plane</ArticleTitle>
<ArticleCategory>Part I Computer Science</ArticleCategory>
<ArticleFirstPage>580</ArticleFirstPage>
<ArticleLastPage>595</ArticleLastPage>
<ArticleHistory><RegistrationDate><Year>2005</Year>
<Month>7</Month>
<Day>9</Day>
</RegistrationDate>
<Received><Year>1992</Year>
<Month>11</Month>
<Day>15</Day>
</Received>
<Revised><Year>1993</Year>
<Month>4</Month>
<Day>15</Day>
</Revised>
</ArticleHistory>
<ArticleCopyright><CopyrightHolderName>the BIT Foundation</CopyrightHolderName>
<CopyrightYear>1993</CopyrightYear>
</ArticleCopyright>
<ArticleGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant>
<AbstractGrant Grant="OpenAccess"></AbstractGrant>
<BodyPDFGrant Grant="Restricted"></BodyPDFGrant>
<BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant>
<BibliographyGrant Grant="Restricted"></BibliographyGrant>
<ESMGrant Grant="Restricted"></ESMGrant>
</ArticleGrants>
<ArticleContext><JournalID>10543</JournalID>
<VolumeIDStart>33</VolumeIDStart>
<VolumeIDEnd>33</VolumeIDEnd>
<IssueIDStart>4</IssueIDStart>
<IssueIDEnd>4</IssueIDEnd>
</ArticleContext>
</ArticleInfo>
<ArticleHeader><AuthorGroup><Author AffiliationIDS="Aff1 Aff2"><AuthorName DisplayOrder="Western"><GivenName>Klaus</GivenName>
<FamilyName>Jansen</FamilyName>
</AuthorName>
</Author>
<Author AffiliationIDS="Aff1 Aff2"><AuthorName DisplayOrder="Western"><GivenName>Gerhard</GivenName>
<GivenName>J.</GivenName>
<FamilyName>Woeginger</FamilyName>
</AuthorName>
</Author>
<Affiliation ID="Aff1"><OrgDivision>Fachbereich IV, Mathematik und Informatik</OrgDivision>
<OrgName>Universität Trier</OrgName>
<OrgAddress><Postbox>Postfach 3825</Postbox>
<Postcode>W-5500</Postcode>
<City>Trier</City>
<Country>Germany</Country>
</OrgAddress>
</Affiliation>
<Affiliation ID="Aff2"><OrgDivision>Institut für Informationsverarbeitung</OrgDivision>
<OrgName>Technische Universität Graz</OrgName>
<OrgAddress><Street>Klosterwiesgasse 32/II</Street>
<Postcode>A-8010</Postcode>
<City>Graz</City>
<Country>Austria</Country>
</OrgAddress>
</Affiliation>
</AuthorGroup>
<Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading>
<Para>The computational complexity of the following type of problem is studied. Given a geometric graph<Emphasis Type="Italic">G</Emphasis>
=(<Emphasis Type="Italic">P, S</Emphasis>
) where<Emphasis Type="Italic">P</Emphasis>
 is a set of points in the Euclidean plane and<Emphasis Type="Italic">S</Emphasis>
 a set of straight (closed) line segments between pairs of points in<Emphasis Type="Italic">P</Emphasis>
, we want to know whether<Emphasis Type="Italic">G</Emphasis>
 possesses a crossingfree subgraph of a special type. We analyze the problem of detecting crossingfree spanning trees, one factors and two factors in the plane. We also consider special restrictions on the slopes and on the lengths of the edges in the subgraphs.</Para>
</Abstract>
<KeywordGroup Language="En"><Heading>AMS categories</Heading>
<Keyword>05C05</Keyword>
<Keyword>68Q25</Keyword>
<Keyword>68R10</Keyword>
</KeywordGroup>
<KeywordGroup Language="En"><Heading>Keywords</Heading>
<Keyword>algorithmic complexity</Keyword>
<Keyword>planar layouts</Keyword>
<Keyword>geometry</Keyword>
</KeywordGroup>
<ArticleNote Type="Misc"><SimplePara>Klaus Jansen acknowledges support by the Deutsche Forschungsgemeinschaft. Gerhard J. Woeginger acknowledges support by the Christian Doppler Laboratorium für Diskrete Optimierung.</SimplePara>
</ArticleNote>
</ArticleHeader>
<NoBody></NoBody>
</Article>
</Issue>
</Volume>
</Journal>
</Publisher>
</istex:document>
</istex:metadataXml>
<mods version="3.6"><titleInfo lang="en"><title>The complexity of detecting crossingfree configurations in the plane</title>
</titleInfo>
<titleInfo type="alternative" contentType="CDATA" lang="en"><title>The complexity of detecting crossingfree configurations in the plane</title>
</titleInfo>
<name type="personal"><namePart type="given">Klaus</namePart>
<namePart type="family">Jansen</namePart>
<affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, W-5500, Trier, Germany</affiliation>
<affiliation>Institut für Informationsverarbeitung, Technische Universität Graz, Klosterwiesgasse 32/II, A-8010, Graz, Austria</affiliation>
<role><roleTerm type="text">author</roleTerm>
</role>
</name>
<name type="personal"><namePart type="given">Gerhard</namePart>
<namePart type="given">J.</namePart>
<namePart type="family">Woeginger</namePart>
<affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, W-5500, Trier, Germany</affiliation>
<affiliation>Institut für Informationsverarbeitung, Technische Universität Graz, Klosterwiesgasse 32/II, A-8010, Graz, Austria</affiliation>
<role><roleTerm type="text">author</roleTerm>
</role>
</name>
<typeOfResource>text</typeOfResource>
<genre type="research-article" displayLabel="OriginalPaper"></genre>
<originInfo><publisher>Kluwer Academic Publishers</publisher>
<place><placeTerm type="text">Dordrecht</placeTerm>
</place>
<dateCreated encoding="w3cdtf">1992-11-15</dateCreated>
<dateIssued encoding="w3cdtf">1993-12-01</dateIssued>
<copyrightDate encoding="w3cdtf">1993</copyrightDate>
</originInfo>
<language><languageTerm type="code" authority="rfc3066">en</languageTerm>
<languageTerm type="code" authority="iso639-2b">eng</languageTerm>
</language>
<physicalDescription><internetMediaType>text/html</internetMediaType>
</physicalDescription>
<abstract lang="en">Abstract: The computational complexity of the following type of problem is studied. Given a geometric graphG=(P, S) whereP is a set of points in the Euclidean plane andS a set of straight (closed) line segments between pairs of points inP, we want to know whetherG possesses a crossingfree subgraph of a special type. We analyze the problem of detecting crossingfree spanning trees, one factors and two factors in the plane. We also consider special restrictions on the slopes and on the lengths of the edges in the subgraphs.</abstract>
<note>Part I Computer Science</note>
<relatedItem type="host"><titleInfo><title>BIT Numerical Mathematics</title>
</titleInfo>
<titleInfo type="abbreviated"><title>BIT</title>
</titleInfo>
<genre type="journal" displayLabel="Archive Journal"></genre>
<originInfo><dateIssued encoding="w3cdtf">1993-12-01</dateIssued>
<copyrightDate encoding="w3cdtf">1993</copyrightDate>
</originInfo>
<subject><genre>Mathematics</genre>
<topic>Numeric Computing</topic>
<topic>Mathematics, general</topic>
<topic>Computational Mathematics and Numerical Analysis</topic>
</subject>
<identifier type="ISSN">0006-3835</identifier>
<identifier type="eISSN">1572-9125</identifier>
<identifier type="JournalID">10543</identifier>
<identifier type="IssueArticleCount">14</identifier>
<identifier type="VolumeIssueCount">4</identifier>
<part><date>1993</date>
<detail type="volume"><number>33</number>
<caption>vol.</caption>
</detail>
<detail type="issue"><number>4</number>
<caption>no.</caption>
</detail>
<extent unit="pages"><start>580</start>
<end>595</end>
</extent>
</part>
<recordInfo><recordOrigin>BIT Foundation, 1993</recordOrigin>
</recordInfo>
</relatedItem>
<identifier type="istex">6597678048C75955853DD52F707557F26EC2DF5D</identifier>
<identifier type="DOI">10.1007/BF01990536</identifier>
<identifier type="ArticleID">BF01990536</identifier>
<identifier type="ArticleID">Art4</identifier>
<accessCondition type="use and reproduction" contentType="copyright">the BIT Foundation, 1993</accessCondition>
<recordInfo><recordContentSource>SPRINGER</recordContentSource>
<recordOrigin>the BIT Foundation, 1993</recordOrigin>
</recordInfo>
</mods>
</metadata>
<serie></serie>
</istex>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001143 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001143 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Rhénanie
   |area=    UnivTrevesV1
   |flux=    Istex
   |étape=   Corpus
   |type=    RBID
   |clé=     ISTEX:6597678048C75955853DD52F707557F26EC2DF5D
   |texte=   The complexity of detecting crossingfree configurations in the plane
}}

This area was generated with Dilib version V0.6.31.
Data generation: Sat Jul 22 16:29:01 2017. Site generation: Wed Feb 28 14:55:37 2024

	Serveur d'exploration sur l'Université de Trèves
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur l'Université de Trèves

The complexity of detecting crossingfree configurations in the plane

The complexity of detecting crossingfree configurations in the plane

Source :

Abstract

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri