Drawing Arrangement Graphs in Small Grids, or How to Play Planarity

Eppstein, David (2013) Drawing Arrangement Graphs in Small Grids, or How to Play Planarity. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 436-447 (Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_38).

Full text not available from this repository.

Abstract

We describe a linear-time algorithm that finds a planar drawing of every graph of a simple line or pseudoline arrangement within a grid of area O(n 7/6). No known input causes our algorithm to use area Ω(n 1 + ε ) for any ε > 0; finding such an input would represent significant progress on the famous k-set problem from discrete geometry. Drawing line arrangement graphs is the main task in the Planarity puzzle.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.720 Straight-line
ID Code:1395

Repository Staff Only: item control page

References

Shor, P.W.: Stretchability of pseudolines is NP-hard. In: Gritzmann, P., Sturmfels, B. (eds.) Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 4, pp. 531–554. Amer. Math. Soc., Providence (1991)

Bose, P., Everett, H., Wismath, S.: Properties of arrangement graphs. International Journal of Computational Geometry & Applications 13(6), 447–462 (2003)

Schaefer, M.: Complexity of some geometric and topological problems. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 334–344. Springer, Heidelberg (2010)

Dolev, D., Leighton, T., Trickey, H.: Planar embedding of planar graphs. Advances in Computing Research 2, 147–161 (1984)

Valiant, L.G.: Universality considerations in VLSI circuits. IEEE Transactions on Computers C-30(2), 135–140 (1981)

Klawe, M., Paterson, M., Pippenger, N.: Inversions with n1+Ω(1/logn√) transpositions at the median (September 21, 1982)(unpublished manuscript)

Tamaki, H., Tokuyama, T.: A characterization of planar graphs by pseudo-line arrangements. Algorithmica 35(3), 269–285 (2003)

Sharir, M., Smorodinsky, S.: Extremal configurations and levels in pseudoline arrangements. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol. 2748, pp. 127–139. Springer, Heidelberg (2003)

Dey, T.L.: Improved bounds for planar k-sets and related problems. Discrete and Computational Geometry 19(3), 373–382 (1998)

Tóth, G.: Point sets with many k-sets. Discrete and Computational Geometry 26(2), 187–194 (2001)

Goodman, J.E.: Pseudoline arrangements. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp. 83–109. CRC Press (1997)

Eppstein, D.: Algorithms for drawing media. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 173–183. Springer, Heidelberg (2005)

Goodman, J.E.: Proof of a conjecture of Burr, Grünbaum, and Sloane. Discrete Mathematics 32(1), 27–35 (1980)

Muthukrishnan, S., Sahinalp, S.C., Paterson, M.S.: Grid layout of switching and sorting networks. US Patent 6185220 (2001)

Bentley, J.L., Ottmann, T.A.: Algorithms for reporting and counting geometric intersections. IEEE Transactions on Computers C-28(9), 643–647 (1979)

Edelsbrunner, H., Guibas, L.J.: Topologically sweeping an arrangement. Journal of Computer and System Sciences 38(1), 165–194 (1989); Corrigendum, JCSS 42(2), 249–251(1991)

Snoeyink, J., Hershberger, J.: Sweeping arrangements of curves. In: Proc. 5th ACM Symp. on Computational Geometry (SCG 1989), pp. 354–363 (1989)

Chrobak, M., Karloff, H.: A lower bound on the size of universal sets for planar graphs. SIGACT News 20, 83–86 (1989)

de Fraysseix, H., Pach, J., Pollack, R.: Small sets supporting Fáry embeddings of planar graphs. In: Proc. 20th ACM Symp. Theory of Computing (STOC 1988), pp. 426–433 (1988)

Schnyder, W.: Embedding planar graphs on the grid. In: Proc. 1st ACM/SIAM Symp. Discrete Algorithms (SODA 1990), pp. 138–148 (1990)

Bannister, M.J., Cheng, Z., Devanny, W.E., Eppstein, D.: Superpatterns and universal point sets. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 208–219. Springer, Heidelberg (2013)

Gritzmann, P., Mohar, B., Pach, J., Pollack, R.: Embedding a planar triangulation with vertices at specified positions. Amer. Math. Monthly 98(2), 165–166 (1991)

Angelini, P., Di Battista, G., Kaufmann, M., Mchedlidze, T., Roselli, V., Squarcella, C.: Small point sets for simply-nested planar graphs. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 75–85. Springer, Heidelberg (2011)

Fulek, R., Tóth, C.D.: Universal point sets for planar three-trees. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol. 8037, pp. 341–352. Springer, Heidelberg (2013)

Khuller, S.: Ear decompositions. SIGACT News 20(1), 128 (1989)