Drawing nice projections of objects in space
Identifieur interne : 001322 ( Istex/Corpus ); précédent : 001321; suivant : 001323Drawing nice projections of objects in space
Auteurs : Prosenjit Bose ; Pedro Ramos ; Francisco Gomez ; Godfried ToussaintSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1996.
Abstract
Abstract: Our results on regular and minimum-crossing projections of line segments have immediate corollaries for polygonal chains, polygons, trees and more general geometric graphs in 3-D since these are all special cases of sets of line segments. Our results also have application to graph drawing for knot-theorists. Let K be a knot with n vertices. To study the knot's combinatorial properties, knot theorists obtain a planar graph G called the diagram of K by a regular projection of K. Many of their algorithms are applied to G and therefore their time complexity depends on the space complexity of G. By combining our algorithms we can obtain regular projections with the minimum number of crossings thereby minimizing the time complexity of their algorithms.
Url:
DOI: 10.1007/BFb0021790
Links to Exploration step
ISTEX:199902040AE0924FDE67AEDBC7767DA79D3A916CLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Drawing nice projections of objects in space</title><author><name sortKey="Bose, Prosenjit" sort="Bose, Prosenjit" uniqKey="Bose P" first="Prosenjit" last="Bose">Prosenjit Bose</name><affiliation><mods:affiliation>University of British Columbia, Vancouver, British Columbia, Canada</mods:affiliation></affiliation></author><author><name sortKey="Ramos, Pedro" sort="Ramos, Pedro" uniqKey="Ramos P" first="Pedro" last="Ramos">Pedro Ramos</name><affiliation><mods:affiliation>Universidad Politecnica de Madrid, Madrid, Spain</mods:affiliation></affiliation></author><author><name sortKey="Gomez, Francisco" sort="Gomez, Francisco" uniqKey="Gomez F" first="Francisco" last="Gomez">Francisco Gomez</name><affiliation><mods:affiliation>Universidad Politecnica de Madrid, Madrid, Spain</mods:affiliation></affiliation></author><author><name sortKey="Toussaint, Godfried" sort="Toussaint, Godfried" uniqKey="Toussaint G" first="Godfried" last="Toussaint">Godfried Toussaint</name><affiliation><mods:affiliation>McGill University, Montreal, Quebec, Canada</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:199902040AE0924FDE67AEDBC7767DA79D3A916C</idno><date when="1996" year="1996">1996</date><idno type="doi">10.1007/BFb0021790</idno><idno type="url">https://api.istex.fr/document/199902040AE0924FDE67AEDBC7767DA79D3A916C/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001322</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001322</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Drawing nice projections of objects in space</title><author><name sortKey="Bose, Prosenjit" sort="Bose, Prosenjit" uniqKey="Bose P" first="Prosenjit" last="Bose">Prosenjit Bose</name><affiliation><mods:affiliation>University of British Columbia, Vancouver, British Columbia, Canada</mods:affiliation></affiliation></author><author><name sortKey="Ramos, Pedro" sort="Ramos, Pedro" uniqKey="Ramos P" first="Pedro" last="Ramos">Pedro Ramos</name><affiliation><mods:affiliation>Universidad Politecnica de Madrid, Madrid, Spain</mods:affiliation></affiliation></author><author><name sortKey="Gomez, Francisco" sort="Gomez, Francisco" uniqKey="Gomez F" first="Francisco" last="Gomez">Francisco Gomez</name><affiliation><mods:affiliation>Universidad Politecnica de Madrid, Madrid, Spain</mods:affiliation></affiliation></author><author><name sortKey="Toussaint, Godfried" sort="Toussaint, Godfried" uniqKey="Toussaint G" first="Godfried" last="Toussaint">Godfried Toussaint</name><affiliation><mods:affiliation>McGill University, Montreal, Quebec, Canada</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>1996</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">199902040AE0924FDE67AEDBC7767DA79D3A916C</idno><idno type="DOI">10.1007/BFb0021790</idno><idno type="ChapterID">7</idno><idno type="ChapterID">Chap7</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Our results on regular and minimum-crossing projections of line segments have immediate corollaries for polygonal chains, polygons, trees and more general geometric graphs in 3-D since these are all special cases of sets of line segments. Our results also have application to graph drawing for knot-theorists. Let K be a knot with n vertices. To study the knot's combinatorial properties, knot theorists obtain a planar graph G called the diagram of K by a regular projection of K. Many of their algorithms are applied to G and therefore their time complexity depends on the space complexity of G. By combining our algorithms we can obtain regular projections with the minimum number of crossings thereby minimizing the time complexity of their algorithms.</div></front></TEI><istex><corpusName>springer</corpusName><author><json:item><name>Prosenjit Bose</name><affiliations><json:string>University of British Columbia, Vancouver, British Columbia, Canada</json:string></affiliations></json:item><json:item><name>Pedro Ramos</name><affiliations><json:string>Universidad Politecnica de Madrid, Madrid, Spain</json:string></affiliations></json:item><json:item><name>Francisco Gomez</name><affiliations><json:string>Universidad Politecnica de Madrid, Madrid, Spain</json:string></affiliations></json:item><json:item><name>Godfried Toussaint</name><affiliations><json:string>McGill University, Montreal, Quebec, Canada</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>ReviewPaper</json:string></originalGenre><abstract>Abstract: Our results on regular and minimum-crossing projections of line segments have immediate corollaries for polygonal chains, polygons, trees and more general geometric graphs in 3-D since these are all special cases of sets of line segments. Our results also have application to graph drawing for knot-theorists. Let K be a knot with n vertices. To study the knot's combinatorial properties, knot theorists obtain a planar graph G called the diagram of K by a regular projection of K. Many of their algorithms are applied to G and therefore their time complexity depends on the space complexity of G. By combining our algorithms we can obtain regular projections with the minimum number of crossings thereby minimizing the time complexity of their algorithms.</abstract><qualityIndicators><score>6.464</score><pdfVersion>1.3</pdfVersion><pdfPageSize>439.28 x 662.28 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>766</abstractCharCount><pdfWordCount>7257</pdfWordCount><pdfCharCount>36105</pdfCharCount><pdfPageCount>12</pdfPageCount><abstractWordCount>122</abstractWordCount></qualityIndicators><title>Drawing nice projections of objects in space</title><chapterId><json:string>7</json:string><json:string>Chap7</json:string></chapterId><refBibs><json:item><author><json:item><name>N,M Amato</name></json:item><json:item><name>M,T Goodrich</name></json:item><json:item><name>E,A Ramos</name></json:item></author><host><author></author><title>Proc. Symp. on the Theory of Computing</title><publicationDate>1995</publicationDate></host><title>Computing faces in segment and simplex arrangements</title><publicationDate>1995</publicationDate></json:item><json:item><author><json:item><name>D Avis</name></json:item><json:item><name>R Wenger</name></json:item></author><host><volume>3</volume><pages><last>265</last><first>257</first></pages><author></author><title>Discrete and Computational Geometry</title><publicationDate>1988</publicationDate></host><title>Polyhedral line transversals in space</title><publicationDate>1988</publicationDate></json:item><json:item><author><json:item><name>D Avis</name></json:item><json:item><name>R Wenger</name></json:item></author><host><pages><last>307</last><first>300</first></pages><author></author><title>Proc. Third ACM Symp. on Computational Geometry</title><publicationDate>1987</publicationDate></host><title>Algorithms for line stabbers in space</title><publicationDate>1987</publicationDate></json:item><json:item><author><json:item><name>I,J Balaban</name></json:item></author><host><pages><last>219</last><first>211</first></pages><author></author><title>Proc. ACM Syrup. on Comp. Geom</title><publicationDate>1995-06</publicationDate></host><title>An optimal algorithm for finding segments intersections</title><publicationDate>1995-06</publicationDate></json:item><json:item><author><json:item><name>J,L Bentley</name></json:item><json:item><name>T,A Ottmann</name></json:item></author><host><volume>8</volume><pages><last>647</last><first>643</first></pages><author></author><title>IEEE Trans. Comput</title><publicationDate>1979</publicationDate></host><title>Algorithms for reporting and counting geometric intersections</title><publicationDate>1979</publicationDate></json:item><json:item><author><json:item><name>P Bhattacharya</name></json:item><json:item><name>A Rosenfeld</name></json:item></author><host><volume>5</volume><pages><last>147</last><first>139</first></pages><author></author><title>J. of Visual Communication and Image Representation</title><publicationDate>1994-06</publicationDate></host><title>Polygons in three dimensions</title><publicationDate>1994-06</publicationDate></json:item><json:item><host><author><json:item><name>J Bondy</name></json:item><json:item><name>U,S R Murty</name></json:item></author><title>Graph Theory with Applications</title><publicationDate>1976</publicationDate></host></json:item><json:item><host><author><json:item><name>T Burger</name></json:item><json:item><name>P Gritzmann</name></json:item><json:item><name>V Klee</name></json:item></author><title>Polytope projection and projection polytopes</title></host></json:item><json:item><author><json:item><name>B Chazelle</name></json:item><json:item><name>H Edelsbrunner</name></json:item></author><host><volume>39</volume><pages><last>54</last><first>1</first></pages><author></author><title>J. ACM</title><publicationDate>1992</publicationDate></host><title>An optimal algorithm for intersecting line segments in the plane</title><publicationDate>1992</publicationDate></json:item><json:item><author><json:item><name>K Chiang</name></json:item><json:item><name>S Nahar</name></json:item><json:item><name>C Lo</name></json:item></author><host><volume>39</volume><pages><last>647</last><first>640</first></pages><author></author><title>IEE Trans. CAD</title><publicationDate>1989</publicationDate></host><title>Time-efficient VLSI artwork analysis algorithms in GOALIE2</title><publicationDate>1989</publicationDate></json:item><json:item><host><author><json:item><name>C Colin</name></json:item></author><title>Automatic computation of a scene's good views</title><publicationDate>1990-02</publicationDate></host></json:item><json:item><author><json:item><name>Di Battista</name></json:item><json:item><name>G Eades</name></json:item><json:item><name>P Tamassia</name></json:item><json:item><name>R Tollis</name></json:item><json:item><name>I,G </name></json:item></author><host><volume>4</volume><pages><last>282</last><first>235</first></pages><author></author><title>Computational Geometry: Theory and Applications</title><publicationDate>1994</publicationDate></host><title>Algorithms for drawing graphs: an annotated bibliography</title><publicationDate>1994</publicationDate></json:item><json:item><host><author><json:item><name>J,D Foley</name></json:item><json:item><name>A Van Dam</name></json:item><json:item><name>S,K Feiner</name></json:item><json:item><name>J,F Hughes</name></json:item></author><title>Computer Graphics: Principles and Practice</title><publicationDate>1990</publicationDate></host></json:item><json:item><host><author><json:item><name>R,S Gallagher</name></json:item><json:item><name>Ed </name></json:item></author><title>Computer Visualization: Graphic Techniques for Engineering and Scientific Analysis</title><publicationDate>1995</publicationDate></host></json:item><json:item><author><json:item><name>M,R Garey</name></json:item><json:item><name>Johnson </name></json:item><json:item><name>D,S </name></json:item></author><host><volume>4</volume><pages><last>316</last><first>312</first></pages><author></author><title>SIAM J. Alg. Discrete Methods</title><publicationDate>1983</publicationDate></host><title>Crossing number is NP-complete</title><publicationDate>1983</publicationDate></json:item><json:item><author><json:item><name>A Garg</name></json:item><json:item><name>R,R Tamassia</name></json:item><json:item><name>I,G Tamassia</name></json:item><json:item><name> Tollis</name></json:item></author><host><pages><last>297</last><first>286</first></pages><author></author><title>Proc. Graph Drawing'94</title><publicationDate>1995</publicationDate></host><title>On the computational complexity of upward and rectilinear planarity testing</title><publicationDate>1995</publicationDate></json:item><json:item><author><json:item><name>T Hirata</name></json:item><json:item><name>J Matousek</name></json:item><json:item><name>X.-H Tan</name></json:item><json:item><name>T Tokuyama</name></json:item></author><host><volume>4</volume><pages><last>308</last><first>293</first></pages><author></author><title>Comp. Geom</title><publicationDate>1994</publicationDate></host><title>Complexity of projected images of convex subdivisions</title><publicationDate>1994</publicationDate></json:item><json:item><author><json:item><name>T Kamada</name></json:item><json:item><name>S Kawai</name></json:item></author><host><volume>41</volume><pages><last>56</last><first>43</first></pages><author></author><title>Computer Vision Graphics and Image Processing</title><publicationDate>1988</publicationDate></host><title>A simple method for computing general position in displaying three-dimensional objects</title><publicationDate>1988</publicationDate></json:item><json:item><host><author><json:item><name>P,R Keller</name></json:item><json:item><name>M,M Keller</name></json:item></author><title>Visual Cues: Practical Data Visualization</title><publicationDate>1993</publicationDate></host></json:item><json:item><host><author><json:item><name>C Livingston</name></json:item><json:item><name>Knot Theory</name></json:item></author><title>The Carus Mathematical Monographs</title><publicationDate>1993</publicationDate></host></json:item><json:item><author><json:item><name>N Megiddo</name></json:item></author><host><volume>12</volume><pages><last>776</last><first>759</first></pages><author></author><title>SIAM Journal of Computing</title><publicationDate>1983</publicationDate></host><title>Linear-time algorithms for linear programming in R 3 and related problems</title><publicationDate>1983</publicationDate></json:item><json:item><author><json:item><name>M Mckenna</name></json:item><json:item><name>R Seidel</name></json:item></author><host><pages><last>28</last><first>24</first></pages><author></author><title>Proc. ACM Syrup. on Comp. Geom</title><publicationDate>1985-06</publicationDate></host><title>Finding the optimal shadows of a convex polytope</title><publicationDate>1985-06</publicationDate></json:item><json:item><author><json:item><name>J Nievergelt</name></json:item><json:item><name>F Preparata</name></json:item></author><host><volume>25</volume><pages><last>747</last><first>739</first></pages><author></author><title>Communications of ACM</title><publicationDate>1982</publicationDate></host><title>Plane-sweep algorithms for intersecting geometric figures</title><publicationDate>1982</publicationDate></json:item><json:item><host><author><json:item><name>F Preparata</name></json:item><json:item><name>M Shamos</name></json:item></author><title>Computational Geometry: An introduction</title><publicationDate>1985</publicationDate></host></json:item><json:item><author><json:item><name>F Preparata</name></json:item><json:item><name>R Tarnassia</name></json:item></author><host><volume>21</volume><pages><last>280</last><first>267</first></pages><author></author><title>SIAM Journal of Computing</title><publicationDate>1992</publicationDate></host><title>Efficient point location in a convex spatial cellcomplex</title><publicationDate>1992</publicationDate></json:item><json:item><author><json:item><name>R Reidemeister</name></json:item><json:item><name> Knotentheorie</name></json:item><json:item><name> Ergebnisse</name></json:item><json:item><name> Mathematic</name></json:item></author><host><volume>I</volume><author></author><title>BSC Associates</title><publicationDate>1932</publicationDate></host><publicationDate>1932</publicationDate></json:item><json:item><author><json:item><name>D Souvaine</name></json:item><json:item><name>I Bjorling-Sachs</name></json:item></author><host><pages><last>1470</last><first>1449</first></pages><author></author><title>Proc. of the IEEE</title><publicationDate>1992</publicationDate></host><title>The contour problem for restricted-orientation polygons</title><publicationDate>1992</publicationDate></json:item><json:item><author><json:item><name>F Shahrokhi</name></json:item><json:item><name>L Szekely</name></json:item><json:item><name>I Vrt 'o</name></json:item></author><host><volume>894</volume><pages><last>142</last><first>131</first></pages><author></author><title>Lecture Notes in Comp. Science</title><publicationDate>1994</publicationDate></host><title>Crossing number of graphs, lower bound techniques and algorithms: A survey</title><publicationDate>1994</publicationDate></json:item><json:item><author><json:item><name>G Strang</name></json:item></author><host><volume>89</volume><pages><last>534</last><first>529</first></pages><issue>8</issue><author></author><title>The American Mathematical Monthly</title><publicationDate>1982-10</publicationDate></host><title>The width of a chair</title><publicationDate>1982-10</publicationDate></json:item><json:item><host><pages><last>375</last><first>335</first></pages><author><json:item><name>G,T Toussaint</name></json:item></author><title>Movable separability of sets</title><publicationDate>1985</publicationDate></host></json:item></refBibs><genre><json:string>conference</json:string></genre><serie><editor><json:item><name>G. Goos</name></json:item><json:item><name>J. Hartmanis</name></json:item><json:item><name>J. van Leeuwen</name></json:item></editor><issn><json:string>0302-9743</json:string></issn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Lecture Notes in Computer Science</title><copyrightDate>1996</copyrightDate></serie><host><editor><json:item><name>Franz J. Brandenburg</name></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Algorithm Analysis and Problem Complexity</value></json:item><json:item><value>Combinatorics</value></json:item><json:item><value>Software Engineering</value></json:item><json:item><value>Computer Graphics</value></json:item><json:item><value>Computer-Aided Engineering (CAD, CAE) and Design</value></json:item><json:item><value>Discrete Mathematics in Computer Science</value></json:item></subject><isbn><json:string>978-3-540-60723-6</json:string></isbn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Graph Drawing</title><bookId><json:string>3540607234</json:string></bookId><volume>1027</volume><pages><last>63</last><first>52</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>book-series</json:string></genre><eisbn><json:string>978-3-540-49351-8</json:string></eisbn><copyrightDate>1996</copyrightDate><doi><json:string>10.1007/BFb0021783</json:string></doi></host><publicationDate>2005</publicationDate><copyrightDate>1996</copyrightDate><doi><json:string>10.1007/BFb0021790</json:string></doi><id>199902040AE0924FDE67AEDBC7767DA79D3A916C</id><score>0.015030429</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/199902040AE0924FDE67AEDBC7767DA79D3A916C/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/199902040AE0924FDE67AEDBC7767DA79D3A916C/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/199902040AE0924FDE67AEDBC7767DA79D3A916C/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Drawing nice projections of objects in space</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>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><p>Springer-Verlag, 1996</p></availability><date>1996</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">Drawing nice projections of objects in space</title><author xml:id="author-1"><persName><forename type="first">Prosenjit</forename><surname>Bose</surname></persName><affiliation>University of British Columbia, Vancouver, British Columbia, Canada</affiliation></author><author xml:id="author-2"><persName><forename type="first">Pedro</forename><surname>Ramos</surname></persName><affiliation>Universidad Politecnica de Madrid, Madrid, Spain</affiliation></author><author xml:id="author-3"><persName><forename type="first">Francisco</forename><surname>Gomez</surname></persName><affiliation>Universidad Politecnica de Madrid, Madrid, Spain</affiliation></author><author xml:id="author-4"><persName><forename type="first">Godfried</forename><surname>Toussaint</surname></persName><affiliation>McGill University, Montreal, Quebec, Canada</affiliation></author></analytic><monogr><title level="m">Graph Drawing</title><title level="m" type="sub">Symposium on Graph Drawing, GD '95 Passau, Germany, September 20–22, 1995 Proceedings</title><idno type="pISBN">978-3-540-60723-6</idno><idno type="eISBN">978-3-540-49351-8</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="DOI">10.1007/BFb0021783</idno><idno type="book-ID">3540607234</idno><idno type="book-title-ID">44941</idno><idno type="book-volume-number">1027</idno><idno type="book-chapter-count">54</idno><editor><persName><forename type="first">Franz</forename><forename type="first">J.</forename><surname>Brandenburg</surname></persName></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2005-06-17"></date><biblScope unit="volume">1027</biblScope><biblScope unit="page" from="52">52</biblScope><biblScope unit="page" to="63">63</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor><persName><forename type="first">G.</forename><surname>Goos</surname></persName></editor><editor><persName><forename type="first">J.</forename><surname>Hartmanis</surname></persName></editor><editor><persName><forename type="first">J.</forename><surname>van Leeuwen</surname></persName></editor><biblScope><date>1996</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="series-Id">558</idno></series><idno type="istex">199902040AE0924FDE67AEDBC7767DA79D3A916C</idno><idno type="DOI">10.1007/BFb0021790</idno><idno type="ChapterID">7</idno><idno type="ChapterID">Chap7</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1996</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: Our results on regular and minimum-crossing projections of line segments have immediate corollaries for polygonal chains, polygons, trees and more general geometric graphs in 3-D since these are all special cases of sets of line segments. Our results also have application to graph drawing for knot-theorists. Let K be a knot with n vertices. To study the knot's combinatorial properties, knot theorists obtain a planar graph G called the diagram of K by a regular projection of K. Many of their algorithms are applied to G and therefore their time complexity depends on the space complexity of G. By combining our algorithms we can obtain regular projections with the minimum number of crossings thereby minimizing the time complexity of their algorithms.</p></abstract><textClass><keywords scheme="Book-Subject-Collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass><keywords scheme="Book-Subject-Group"><list><label>I</label><label>I16021</label><label>M17009</label><label>I14029</label><label>I22013</label><label>I23044</label><label>I17028</label><item><term>Computer Science</term></item><item><term>Algorithm Analysis and Problem Complexity</term></item><item><term>Combinatorics</term></item><item><term>Software Engineering</term></item><item><term>Computer Graphics</term></item><item><term>Computer-Aided Engineering (CAD, CAE) and Design</term></item><item><term>Discrete Mathematics in Computer Science</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2005-06-17">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-11-23">References added</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2017-01-21">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/199902040AE0924FDE67AEDBC7767DA79D3A916C/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>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle><SeriesAbbreviatedTitle>Lect Notes Comput Sci</SeriesAbbreviatedTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>G.</GivenName><FamilyName>Goos</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>J.</GivenName><FamilyName>Hartmanis</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>J.</GivenName><Particle>van</Particle><FamilyName>Leeuwen</FamilyName></EditorName></Editor></EditorGroup></SeriesHeader><Book Language="En"><BookInfo MediaType="eBook" Language="En" BookProductType="Proceedings" TocLevels="0" NumberingStyle="Unnumbered"><BookID>3540607234</BookID><BookTitle>Graph Drawing</BookTitle><BookSubTitle>Symposium on Graph Drawing, GD '95 Passau, Germany, September 20–22, 1995 Proceedings</BookSubTitle><BookVolumeNumber>1027</BookVolumeNumber><BookDOI>10.1007/BFb0021783</BookDOI><BookTitleID>44941</BookTitleID><BookPrintISBN>978-3-540-60723-6</BookPrintISBN><BookElectronicISBN>978-3-540-49351-8</BookElectronicISBN><BookChapterCount>54</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1996</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I16021" Priority="1" Type="Secondary">Algorithm Analysis and Problem Complexity</BookSubject><BookSubject Code="M17009" Priority="2" Type="Secondary">Combinatorics</BookSubject><BookSubject Code="I14029" Priority="3" Type="Secondary">Software Engineering</BookSubject><BookSubject Code="I22013" Priority="4" Type="Secondary">Computer Graphics</BookSubject><BookSubject Code="I23044" Priority="5" Type="Secondary">Computer-Aided Engineering (CAD, CAE) and Design</BookSubject><BookSubject Code="I17028" Priority="6" Type="Secondary">Discrete Mathematics in Computer Science</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup></BookInfo><BookHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Franz</GivenName><GivenName>J.</GivenName><FamilyName>Brandenburg</FamilyName></EditorName></Editor></EditorGroup></BookHeader><Chapter ID="Chap7" Language="En"><ChapterInfo ChapterType="ReviewPaper" NumberingStyle="Unnumbered" TocLevels="0" ContainsESM="No"><ChapterID>7</ChapterID><ChapterDOI>10.1007/BFb0021790</ChapterDOI><ChapterSequenceNumber>7</ChapterSequenceNumber><ChapterTitle Language="En">Drawing nice projections of objects in space</ChapterTitle><ChapterFirstPage>52</ChapterFirstPage><ChapterLastPage>63</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1996</CopyrightYear></ChapterCopyright><ChapterHistory><OnlineDate><Year>2005</Year><Month>6</Month><Day>17</Day></OnlineDate></ChapterHistory><ChapterGrants 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></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><BookID>3540607234</BookID><BookTitle>Graph Drawing</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Prosenjit</GivenName><FamilyName>Bose</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>Pedro</GivenName><FamilyName>Ramos</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>Francisco</GivenName><FamilyName>Gomez</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff3"><AuthorName DisplayOrder="Western"><GivenName>Godfried</GivenName><FamilyName>Toussaint</FamilyName></AuthorName></Author><Affiliation ID="Aff1"><OrgName>University of British Columbia</OrgName><OrgAddress><City>Vancouver</City><State>British Columbia</State><Country>Canada</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>Universidad Politecnica de Madrid</OrgName><OrgAddress><City>Madrid</City><Country>Spain</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgName>McGill University</OrgName><OrgAddress><City>Montreal</City><State>Quebec</State><Country>Canada</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>Our results on regular and minimum-crossing projections of line segments have immediate corollaries for polygonal chains, polygons, trees and more general geometric graphs in 3-D since these are all special cases of sets of line segments. Our results also have application to graph drawing for knot-theorists. Let <Emphasis Type="Italic">K</Emphasis> be a knot with <Emphasis Type="Italic">n</Emphasis> vertices. To study the knot's combinatorial properties, knot theorists obtain a planar graph <Emphasis Type="Italic">G</Emphasis> called the diagram of <Emphasis Type="Italic">K</Emphasis> by a regular projection of <Emphasis Type="Italic">K</Emphasis>. Many of their algorithms are applied to <Emphasis Type="Italic">G</Emphasis> and therefore their time complexity depends on the space complexity of <Emphasis Type="Italic">G</Emphasis>. By combining our algorithms we can obtain regular projections with the minimum number of crossings thereby minimizing the time complexity of their algorithms.</Para></Abstract><ArticleNote Type="Misc"><SimplePara>Research of the first author was supported by an NSERC & Killam Fellowship. Research of the second and third authors was carried out during their visit to McGill University in 1995 and was self-supported. The fourth author was supported by NSERC Grant no. OGP0009293 and FCAR Grant no. 93-ER-0291.</SimplePara></ArticleNote></ChapterHeader><NoBody></NoBody></Chapter></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Drawing nice projections of objects in space</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>Drawing nice projections of objects in space</title></titleInfo><name type="personal"><namePart type="given">Prosenjit</namePart><namePart type="family">Bose</namePart><affiliation>University of British Columbia, Vancouver, British Columbia, Canada</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Pedro</namePart><namePart type="family">Ramos</namePart><affiliation>Universidad Politecnica de Madrid, Madrid, Spain</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Francisco</namePart><namePart type="family">Gomez</namePart><affiliation>Universidad Politecnica de Madrid, Madrid, Spain</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Godfried</namePart><namePart type="family">Toussaint</namePart><affiliation>McGill University, Montreal, Quebec, Canada</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="conference" displayLabel="ReviewPaper"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2005-06-17</dateIssued><copyrightDate encoding="w3cdtf">1996</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: Our results on regular and minimum-crossing projections of line segments have immediate corollaries for polygonal chains, polygons, trees and more general geometric graphs in 3-D since these are all special cases of sets of line segments. Our results also have application to graph drawing for knot-theorists. Let K be a knot with n vertices. To study the knot's combinatorial properties, knot theorists obtain a planar graph G called the diagram of K by a regular projection of K. Many of their algorithms are applied to G and therefore their time complexity depends on the space complexity of G. By combining our algorithms we can obtain regular projections with the minimum number of crossings thereby minimizing the time complexity of their algorithms.</abstract><relatedItem type="host"><titleInfo><title>Graph Drawing</title><subTitle>Symposium on Graph Drawing, GD '95 Passau, Germany, September 20–22, 1995 Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Franz</namePart><namePart type="given">J.</namePart><namePart type="family">Brandenburg</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">1996</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I16021">Algorithm Analysis and Problem Complexity</topic><topic authority="SpringerSubjectCodes" authorityURI="M17009">Combinatorics</topic><topic authority="SpringerSubjectCodes" authorityURI="I14029">Software Engineering</topic><topic authority="SpringerSubjectCodes" authorityURI="I22013">Computer Graphics</topic><topic authority="SpringerSubjectCodes" authorityURI="I23044">Computer-Aided Engineering (CAD, CAE) and Design</topic><topic authority="SpringerSubjectCodes" authorityURI="I17028">Discrete Mathematics in Computer Science</topic></subject><identifier type="DOI">10.1007/BFb0021783</identifier><identifier type="ISBN">978-3-540-60723-6</identifier><identifier type="eISBN">978-3-540-49351-8</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">44941</identifier><identifier type="BookID">3540607234</identifier><identifier type="BookChapterCount">54</identifier><identifier type="BookVolumeNumber">1027</identifier><part><date>1996</date><detail type="volume"><number>1027</number><caption>vol.</caption></detail><extent unit="pages"><start>52</start><end>63</end></extent></part><recordInfo><recordOrigin>Springer-Verlag, 1996</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">G.</namePart><namePart type="family">Goos</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">J.</namePart><namePart type="family">Hartmanis</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">J.</namePart><namePart type="family">van Leeuwen</namePart><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">1996</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag, 1996</recordOrigin></recordInfo></relatedItem><identifier type="istex">199902040AE0924FDE67AEDBC7767DA79D3A916C</identifier><identifier type="DOI">10.1007/BFb0021790</identifier><identifier type="ChapterID">7</identifier><identifier type="ChapterID">Chap7</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag, 1996</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag, 1996</recordOrigin></recordInfo></mods></metadata></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 001322 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001322 | 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:199902040AE0924FDE67AEDBC7767DA79D3A916C
|texte= Drawing nice projections of objects in space
}}
| This area was generated with Dilib version V0.6.31. |  |