{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,13]],"date-time":"2025-12-13T06:45:18Z","timestamp":1765608318548},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540589501"},{"type":"electronic","value":"9783540491552"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-58950-3_375","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:54:34Z","timestamp":1330257274000},"page":"234-245","source":"Crossref","is-referenced-by-count":4,"title":["Characterization and recognition of point-halfspace and related orders"],"prefix":"10.1007","author":[{"given":"Paul J.","family":"Tanenbaum","sequence":"first","affiliation":[]},{"given":"Michael T.","family":"Goodrich","sequence":"additional","affiliation":[]},{"given":"Edward R.","family":"Scheinerman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"25_CR1","doi-asserted-by":"crossref","unstructured":"P. Bertolazzi, R. F. Cohen, G. Di Battista, R. Tamassia, and I. G. Tollis. How to draw a series-parallel digraph. In Proc. 3rd Scand. Workshop Algorithm Theory, volume 621 of Lecture Notes in Computer Science, pages 272\u2013283. Springer-Verlag, 1992.","DOI":"10.1007\/3-540-55706-7_23"},{"key":"25_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph Theory with Applications","author":"J. A. Bondy","year":"1976","unstructured":"John Adrian Bondy and U. S. R. Murty. Graph Theory with Applications. North-Holland, New York, 1976."},{"key":"25_CR3","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. S. Booth","year":"1976","unstructured":"Kellogg S. Booth and George S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. System Sci., 13:335\u2013379, 1976.","journal-title":"J. Comput. System Sci."},{"key":"25_CR4","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/BF00563524","volume":"6","author":"G. Brightwell","year":"1989","unstructured":"Graham Brightwell and Peter Winkler. Sphere orders. Order, 6:235\u2013240, 1989.","journal-title":"Order"},{"issue":"1","key":"25_CR5","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/0022-0000(85)90004-2","volume":"30","author":"N. Chiba","year":"1985","unstructured":"N. Chiba, T. Nishizeki, S. Abe, and T. Ozawa. A linear algorithm for embedding planar graphs using PQ-trees. J. Comput. System Sci., 30(1):54\u201376, 1985.","journal-title":"J. Comput. System Sci."},{"key":"25_CR6","unstructured":"P. A. Colley. Recognizing visibility graphs of uni-monotone polygons. In Proc. 4th Canad. Conf. Comput. Geom., pages 29\u201334, 1992."},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"J. Czyzowicz, I. Rival, and J. Urrutia. Galleries, light matchings and visibility graphs. In Proc. 1st Workshop Algorithms Data Struct., volume 382 of Lecture Notes in Computer Science, pages 316\u2013324. Springer-Verlag, 1989.","DOI":"10.1007\/3-540-51542-9_27"},{"key":"25_CR8","first-page":"75","volume":"13","author":"H. Fraysseix de","year":"1982","unstructured":"H. de Fraysseix and P. Rosenstiehl. A depth-first-search characterization of planarity. Ann. Discrete Math., 13:75\u201380, 1982.","journal-title":"Ann. Discrete Math."},{"key":"25_CR9","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/321921.321929","volume":"23","author":"N. Deo","year":"1976","unstructured":"N. Deo. Note on Hopcroft and Tarjan's planarity algorithm. J. ACM, 23:74\u201375, 1976.","journal-title":"J. ACM"},{"key":"25_CR10","volume-title":"Algorithms for drawing graphs: an annotated bibliography","author":"G. Battista Di","year":"1993","unstructured":"G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Algorithms for drawing graphs: an annotated bibliography. Preprint, Dept. Comput. Sci., Brown Univ., Providence, RI, November 1993. To appear in Comput. Geom. Theory Appl. Preliminary version available via anonymous ftp from wilma.cs.brown.edu, gdbiblio.tex.Z and gdbiblio.ps.Z in \/pub\/papers\/compgeo."},{"key":"25_CR11","doi-asserted-by":"crossref","first-page":"600","DOI":"10.2307\/2371374","volume":"63","author":"B. Dushnik","year":"1941","unstructured":"B. Dushnik and E. W. Miller. Partially ordered sets. Amer. J. Math., 63:600\u2013610, 1941.","journal-title":"Amer. J. Math."},{"issue":"1","key":"25_CR12","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0890-5401(92)90041-D","volume":"98","author":"D. Eppstein","year":"1992","unstructured":"David Eppstein. Parallel recognition of series-parallel graphs. Inform. and Comput, 98(1):41\u201355, May 1992.","journal-title":"Inform. and Comput"},{"key":"25_CR13","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/0304-3975(76)90086-4","volume":"2","author":"S. Even","year":"1976","unstructured":"S. Even and R. E. Tarjan. Computing an st-numbering. Theoret. Comput. Sci., 2:339\u2013344, 1976.","journal-title":"Theoret. Comput. Sci."},{"key":"25_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0196-6774(90)90026-B","volume":"11","author":"H. Everett","year":"1990","unstructured":"H. Everett and D. G. Corneil. Recognizing visibility graphs of spiral polygons. J. Algorithms, 11:1\u201326, 1990.","journal-title":"J. Algorithms"},{"key":"25_CR15","volume-title":"Interval Orders and Interval Graphs: A Study of Partially Ordered Sets","author":"P. C. Fishburn","year":"1985","unstructured":"Peter C. Fishburn. Interval Orders and Interval Graphs: A Study of Partially Ordered Sets. John Wiley, New York, 1985."},{"key":"25_CR16","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/BF00582739","volume":"1","author":"P. C. Fishburn","year":"1985","unstructured":"Peter C. Fishburn and William Thomas Trotter. Angle orders. Order, 1:333\u2013343, 1985.","journal-title":"Order"},{"key":"25_CR17","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979."},{"key":"25_CR18","unstructured":"Ashim Garg and Roberto Tamassia. On the computational complexity of upward and rectilinear planarity testing. Technical Report CS-94-10, Brown University, 1994."},{"key":"25_CR19","doi-asserted-by":"crossref","unstructured":"S. K. Ghosh. On recognizing and characterizing visibility graphs of simple polygons. In Proc. 1st Scand. Workshop Algorithm Theory, volume 318 of Lecture Notes in Computer Science, pages 96\u2013104. Springer-Verlag, 1988.","DOI":"10.1007\/3-540-19487-8_10"},{"key":"25_CR20","doi-asserted-by":"crossref","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"P. C. Gilmore","year":"1964","unstructured":"P. C. Gilmore and A. J. Hoffman. A characterization of comparability graphs and of interval graphs. Canad. J. Math., 16:539\u2013548, 1964.","journal-title":"Canad. J. Math."},{"key":"25_CR21","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0097-3165(84)90050-5","volume":"37","author":"J. E. Goodman","year":"1984","unstructured":"Jacob E. Goodman and Richard Pollack. Semispaces of configurations, cell complexes of arrangements. J. Combin. Theory Ser. A, 37:257\u2013293, 1984.","journal-title":"J. Combin. Theory Ser. A"},{"key":"25_CR22","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"J. Hopcroft and R. E. Tarjan. Efficient planarity testing. J. Assoc. Comput. Mach., 21:549\u2013568, 1974.","journal-title":"J. Assoc. Comput. Mach."},{"key":"25_CR23","doi-asserted-by":"crossref","unstructured":"Korte and M\u00f6hring. An incremental linear-time algorithm for recognizing interval graphs. SIAM J. Comput., 18, 1989.","DOI":"10.1137\/0218005"},{"key":"25_CR24","doi-asserted-by":"crossref","unstructured":"D. Kozen, U. Vazirani, and V. Vazirani. NC algorithms for comparability graphs, interval graphs, and testing for unique perfect matching. Foundations of Software Technology and Theoretical Computer Science, 1985.","DOI":"10.1007\/3-540-16042-6_28"},{"key":"25_CR25","doi-asserted-by":"crossref","unstructured":"Ramalingam and Rangan. New sequential and parallel algorithms for interval graph recognition. Inform. Process. Lett., 34, 1990.","DOI":"10.1016\/0020-0190(90)90163-R"},{"key":"25_CR26","unstructured":"Edward R. Scheinerman, Ann N. Trenk, and Daniel Ullman. On point-halfspace graphs. J. Graph Theory, to appear."},{"key":"25_CR27","first-page":"531","volume-title":"Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, volume 4 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science","author":"P. W. Shor","year":"1991","unstructured":"Peter W. Shor. Stretchability of pseudolines is NP-hard. In P. Gritzman and B. Sturmfels, editors, Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, volume 4 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 531\u2013554. Amer. Math. Soc., Providence, R.I., 1991."},{"key":"25_CR28","first-page":"289","volume-title":"Computational Geometry-Methods, Algorithms and Applications, International Workshop on Computational Geometry CG '91, number 553 in Lecture Notes in Computer Science","author":"K. Simon","year":"1991","unstructured":"Klaus Simon. A new simple linear algorithm to recognize interval graphs. In Computational Geometry-Methods, Algorithms and Applications, International Workshop on Computational Geometry CG '91, number 553 in Lecture Notes in Computer Science, pages 289\u2013308. Springer-Verlag, Berlin, 1991."},{"key":"25_CR29","doi-asserted-by":"crossref","unstructured":"Jeremy Spinrad. On comparability and permutation graphs. SIAM J. Comput., 1985.","DOI":"10.1137\/0214048"},{"key":"25_CR30","first-page":"676","volume-title":"Automata, Languages and Programming, 10th Colloquium, number 154 in Lecture Notes in Computer Science","author":"J. Spinrad","year":"1983","unstructured":"Jeremy Spinrad and Jacobo Valdes. Recognition and isomorphism of two dimensional partial orders. In Automata, Languages and Programming, 10th Colloquium, number 154 in Lecture Notes in Computer Science, pages 676\u2013686. Springer-Verlag, Berlin, 1983."},{"key":"25_CR31","volume-title":"Johns Hopkins Series in Mathematical Sciences","author":"W. T. Trotter","year":"1992","unstructured":"William Thomas Trotter. Combinatorics and Partially Ordered Sets: Dimension Theory. Johns Hopkins Series in Mathematical Sciences. Johns Hopkins Univ. Press, Baltimore, 1992."},{"key":"25_CR32","doi-asserted-by":"crossref","unstructured":"J. Valdes, R. Tarjan, and E. Lawler. The recognition of series parallel digraphs. In Proc. 11th ACM Symposium on Theory of Computing (STOC), pages 1\u201312, 1979.","DOI":"10.1145\/800135.804393"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58950-3_375.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:24:51Z","timestamp":1605630291000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58950-3_375"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540589501","9783540491552"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/3-540-58950-3_375","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}