Characterization and Recognition of Point-Halfspace and Related Orders (Preliminary Version)

Tanenbaum, Paul J. and Goodrich, Michael T. and Scheinerman, Edward R. (1995) Characterization and Recognition of Point-Halfspace and Related Orders (Preliminary Version). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 234-245 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_375).

Full text not available from this repository.

Abstract

We characterize four classes of geometric membership and containment orders-structurally and in terms of forbidden subposets-and present linear- or near linear-time recognition algorithms for each class. We also show that recognizing point-halfspace orders in \mathbb{R}^{d} is NP-hard for d \geq 2.

Item Type:Conference Paper
Additional Information:10.1007/3-540-58950-3_375
Classifications:Z Theory > Z.250 Geometry
G Algorithms and Complexity > G.560 Geometry
ID Code:167

Repository Staff Only: item control page

References

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-283. Springer-Verlag, 1992.

John Adrian Bondy and U. S. R. Murty. Graph Theory with Applications. North-Holland, New York, 1976.

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-379, 1976.

Graham Brightwell and Peter Winkler. Sphere orders. Order, 6:235-240, 1989.

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-76, 1985.

P. A. Colley. Recognizing visibility graphs of uni-monotone polygons. In Proc. 4th Canad. Conf. Comput. Geom., pages 29-34, 1992.

J. Czyzowicz, I. Rival, and J. Urrutia. Galleries, light matchings and visibility graphs. In Proc. 1st Worshop Algorithms Data Struct., volume 382 of Lecture Notes in Computer Science, pages 316-324. Springer-Verlag, 1989.

H. de Fraysseix and P. Rosenstiehl. A depth-first-search characterization of planarity. Ann. Discrete Math., 13:75-80, 1982.

N. Deo. Note on Hopcroft and Tarjan's planarity algorithm. J. ACM, 23:74-75, 1976.

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.

B. Dushnik and E. W. Miller. Partially ordered sets. Amer. J. Math., 63:600-610, 1941.

David Eppstein. Parallel recognition of series-parallel graphs. Inform. and Comput., 98(1):41-55, May 1992.

S. Even and R. E. Tarjan. Computing an st-numbering. Theoret. Comput. Sci., 2:339-344, 1976.

H. Everett and D. G. Corneil. Recognizing visibility graphs of spiral polygons. J. Algorithms, 11:1-26, 1990.

Peter C. Fishburn. Interval Orders and Interval Graphs: A Study of Partially Ordered DSets. John Wiley, New York, 1985.

Peter C. Fishburn and William Thomas Trotter. Angle orders. Order, 1:333-343, 1985.

Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979.

Ashim Garg and Roberto Tamassia. On the computational complexity of upward, and rectilinear planarity testing. Technical Report CS-94-10, Brown University, 1994.

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-104. Springer-Verlag, 1988.

P. C. Gilmore and A. J. Hoffman. A characterization of comparability graphs and of interval graphs. Canad. J. Math., 16:539-548, 1964.

Jacob E. Goodam and Richard Pollack. Semispaces of configurations, cell complexes of arrangements. J. Combin. Theory Ser. A, 37:257-293, 1984.

J. Hopcroft and R. E. Tarjan. Efficient planarity testing. J. Assoc. Comput. Mach., 21:549-568, 1974.

Korte and Möhring. An incremental linear-time algorithm for recognizing interval graphs. SIAM J. Comput., 18, 1989.

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.

Ramalingam and Rangan. New sequential and parallel algorithms for interval graph recognition. Inform. Process. Lett., 34, 1990.

Edward R. Scheinerman, Ann N. Trenk, and Daniel Ullman. On point-halfspace graphs. J. Graph Theory, to appear.

Peter W. Shor. Strechability 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-554. Amer. Math. Soc., Providence, R.I., 1991.

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 on Lecture Notes in Computer Science, pages 289-308. Springer-Verlag, Berlin 1991.

Jeremy Spinrad. On comparability and permutation graphs. SIAM J. Comput., 1985.

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-686. Springer-Verlag, Berlin, 1983.

William Thomas Trotter. Combinatorics and Partially Ordered Sets: Dimension Theory. Johns Hopkins Series in Mathematical Sciences. John Hopkins Univ. Press, Baltimore, 1992.

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-12, 1979.