{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T09:27:36Z","timestamp":1774690056000,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":73,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642114083","type":"print"},{"value":"9783642114090","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11409-0_1","type":"book-chapter","created":{"date-parts":[[2009,12,3]],"date-time":"2009-12-03T13:12:27Z","timestamp":1259845947000},"page":"1-16","source":"Crossref","is-referenced-by-count":23,"title":["Graph-Theoretic Solutions to Computational Geometry Problems"],"prefix":"10.1007","author":[{"given":"David","family":"Eppstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"1_CR1","doi-asserted-by":"publisher","first-page":"912","DOI":"10.1137\/S0097539795295936","volume":"29","author":"P.K. Agarwal","year":"2000","unstructured":"Agarwal, P.K., Efrat, A., Sharir, M.: Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications. SIAM J. Comput.\u00a029(3), 912\u2013953 (2000)","journal-title":"SIAM J. Comput."},{"key":"1_CR2","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0012-365X(95)00349-2","volume":"152","author":"A.A. Ageev","year":"1996","unstructured":"Ageev, A.A.: A triangle-free circle graph with chromatic number 5. Discrete Mathematics\u00a0152, 295\u2013298 (1996)","journal-title":"Discrete Mathematics"},{"issue":"1","key":"1_CR3","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/0196-6774(91)90022-Q","volume":"12","author":"A. Aggarwal","year":"1991","unstructured":"Aggarwal, A., Imai, H., Katoh, N., Suri, S.: Finding k points with minimum diameter and related problems. J. Algorithms\u00a012(1), 38\u201356 (1991)","journal-title":"J. Algorithms"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Chv\u00e1tal, V., Newborn, M., Szemer\u00e9di, E.: Crossing-free subgraphs. In: Theory and Practice of Combinatorics. North-Holland Mathematics Studies, vol.\u00a060, pp. 9\u201312 (1982)","DOI":"10.1016\/S0304-0208(08)73484-4"},{"issue":"9","key":"1_CR5","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1007\/BF01782475","volume":"12","author":"E.M. Arkin","year":"1996","unstructured":"Arkin, E.M., Held, M., Mitchell, J.S.B., Skiena, S.S.: Hamiltonian triangulations for fast rendering. The Visual Computer\u00a012(9), 429\u2013444 (1996)","journal-title":"The Visual Computer"},{"key":"1_CR6","unstructured":"Bandelt, H.-J., Chepoi, V., Eppstein, D.: Combinatorics and geometry of finite and infinite squaregraphs. Electronic preprint arxiv:0905.4537 (2009)"},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1006\/jagm.2000.1132","volume":"38","author":"T.C. Biedl","year":"2001","unstructured":"Biedl, T.C., Bose, P., Demaine, E.D., Lubiw, A.: Efficient algorithms for Petersen\u2019s matching theorem. J. Algorithms\u00a038, 110\u2013134 (2001)","journal-title":"J. Algorithms"},{"issue":"1\u20132","key":"1_CR8","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0925-7721(97)00014-X","volume":"9","author":"H. Breu","year":"1998","unstructured":"Breu, H., Kirkpatrick, D.G.: Unit disk graph recognition is NP-hard. Computational Geometry Theory and Applications\u00a09(1\u20132), 3\u201324 (1998)","journal-title":"Computational Geometry Theory and Applications"},{"key":"1_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-540-70904-6_9","volume-title":"Graph Drawing","author":"J. Carlson","year":"2007","unstructured":"Carlson, J., Eppstein, D.: Trees with convex faces and optimal angles. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol.\u00a04372, pp. 77\u201388. Springer, Heidelberg (2007)"},{"issue":"1","key":"1_CR10","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/BF02574703","volume":"6","author":"B. Chazelle","year":"1991","unstructured":"Chazelle, B.: Triangulating a simple polygon in linear time. Discrete & Computational Geometry\u00a06(1), 485\u2013524 (1991)","journal-title":"Discrete & Computational Geometry"},{"issue":"5","key":"1_CR11","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1109\/32.6142","volume":"14","author":"Y. Cheng","year":"1988","unstructured":"Cheng, Y., Iyengar, S.S., Kashyap, R.L.: A new method of image compression using irreducible covers of maximal rectangles. IEEE Trans. Software Engineering\u00a014(5), 651\u2013658 (1988)","journal-title":"IEEE Trans. Software Engineering"},{"key":"1_CR12","first-page":"346","volume-title":"Proc. 13th Annu. ACM\u2013SIAM Symp. on Discrete Algorithms (SODA 2002)","author":"V. Chepoi","year":"2002","unstructured":"Chepoi, V., Dragan, F., Vax\u00e8s, Y.: Center and diameter problem in planar quadrangulations and triangulations. In: Proc. 13th Annu. ACM\u2013SIAM Symp. on Discrete Algorithms (SODA 2002), pp. 346\u2013355. ACM Press, New York (2002)"},{"key":"1_CR13","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(75)90061-1","volume":"18","author":"V. Chv\u00e1tal","year":"1975","unstructured":"Chv\u00e1tal, V.: A combinatorial theorem in plane geometry. Journal of Combinatorial Theory, Series B\u00a018, 39\u201341 (1975)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"1_CR14","series-title":"Annals of Discrete Mathematics","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0304-0208(08)72923-2","volume-title":"Topics in Perfect Graphs","author":"V. Chv\u00e1tal","year":"1984","unstructured":"Chv\u00e1tal, V.: Perfectly orderable graphs. In: Berge, C., Chv\u00e1tal, V. (eds.) Topics in Perfect Graphs. Annals of Discrete Mathematics, vol.\u00a021, pp. 63\u201368. North-Holland, Amsterdam (1984)"},{"key":"1_CR15","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"B.N. Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Mathematics\u00a086, 165\u2013177 (1990)","journal-title":"Discrete Mathematics"},{"key":"1_CR16","first-page":"38","volume":"43","author":"N.G. Bruijn de","year":"1981","unstructured":"de Bruijn, N.G.: Algebraic theory of Penrose\u2019s non-periodic tilings of the plane. Indagationes Mathematicae\u00a043, 38\u201366 (1981)","journal-title":"Indagationes Mathematicae"},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"Deering, M.: Geometry compression. In: Proc. 22nd Conf. Computer Graphics and Interactive Techniques (SIGGRAPH), pp. 13\u201320 (1995)","DOI":"10.1145\/218380.218391"},{"issue":"3","key":"1_CR18","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/PL00009354","volume":"19","author":"T.K. Dey","year":"1998","unstructured":"Dey, T.K.: Improved bounds for planar k-sets and related problems. Discrete & Computational Geometry\u00a019(3), 373\u2013382 (1998)","journal-title":"Discrete & Computational Geometry"},{"key":"1_CR19","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"G. Battista Di","year":"1998","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Englewood Cliffs (1998)"},{"key":"1_CR20","unstructured":"D\u00edaz-Guti\u00e9rrez, P.: Using graph algorithms for geometry processing on surfaces. PhD thesis, Univ. of California, Irvine (2009)"},{"issue":"9","key":"1_CR21","doi-asserted-by":"publisher","first-page":"2015","DOI":"10.1016\/j.dam.2008.12.008","volume":"157","author":"K. Engel","year":"2009","unstructured":"Engel, K.: Optimal matrix-segmentation by rectangles. Discrete Applied Mathematics\u00a0157(9), 2015\u20132030 (2009)","journal-title":"Discrete Applied Mathematics"},{"key":"1_CR22","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/PL00009396","volume":"20","author":"D. Eppstein","year":"1998","unstructured":"Eppstein, D.: Geometric lower bounds for parametric matroid optimization. Discrete & Computational Geometry\u00a020, 463\u2013476 (1998)","journal-title":"Discrete & Computational Geometry"},{"key":"1_CR23","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/B978-044482537-7\/50010-3","volume-title":"Handbook of Computational Geometry","author":"D. Eppstein","year":"2000","unstructured":"Eppstein, D.: Spanning trees and spanners. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, ch.\u00a09, pp. 425\u2013461. Elsevier, Amsterdam (2000)"},{"key":"1_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/978-3-540-31843-9_19","volume-title":"Graph Drawing","author":"D. Eppstein","year":"2005","unstructured":"Eppstein, D.: Algorithms for drawing media. In: Pach, J. (ed.) GD 2004. LNCS, vol.\u00a03383, pp. 173\u2013183. Springer, Heidelberg (2005)"},{"issue":"1","key":"1_CR25","doi-asserted-by":"crossref","first-page":"61","DOI":"10.7155\/jgaa.00137","volume":"11","author":"D. Eppstein","year":"2007","unstructured":"Eppstein, D.: The traveling salesman problem for cubic graphs. J. Graph Algorithms and Applications\u00a011(1), 61\u201381 (2007)","journal-title":"J. Graph Algorithms and Applications"},{"issue":"2","key":"1_CR26","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/1497290.1497291","volume":"5","author":"D. Eppstein","year":"2009","unstructured":"Eppstein, D.: Testing bipartiteness of geometric intersection graphs. ACM Trans. Algorithms\u00a05(2), 15 (2009)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"1_CR27","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF02574012","volume":"11","author":"D. Eppstein","year":"1994","unstructured":"Eppstein, D., Erickson, J.: Iterated nearest neighbors and finding minimal polytopes. Discrete & Computational Geometry\u00a011(3), 321\u2013350 (1994)","journal-title":"Discrete & Computational Geometry"},{"key":"1_CR28","volume-title":"Media Theory","author":"D. Eppstein","year":"2007","unstructured":"Eppstein, D., Falmagne, J.-C., Ovchinnikov, S.: Media Theory. Springer, Heidelberg (2007)"},{"issue":"3","key":"1_CR29","first-page":"371","volume":"23","author":"D. Eppstein","year":"2004","unstructured":"Eppstein, D., Gopi, M.: Single-strip triangulation of manifolds with arbitrary topology. Eurographics Forum\u00a023(3), 371\u2013379 (2004); Proc. 25th Conf. Eur. Assoc. for Computer Graphics (EuroGraphics 2004)","journal-title":"Eurographics Forum"},{"key":"1_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1007\/978-3-642-03367-4_24","volume-title":"WADS 2009","author":"D. Eppstein","year":"2009","unstructured":"Eppstein, D., Mumford, E.: Orientation-constrained rectangular layouts. In: Dehne, F., et al. (eds.) WADS 2009. LNCS, vol.\u00a05664, pp. 266\u2013277. Springer, Heidelberg (2009)"},{"key":"1_CR31","doi-asserted-by":"crossref","unstructured":"Eppstein, D., Mumford, E., Speckmann, B., Verbeek, K.A.B.: Area-universal rectangular layouts. In: Proc. 25th ACM Symp. Computational Geometry, pp. 267\u2013276 (2009)","DOI":"10.1145\/1542362.1542411"},{"key":"1_CR32","unstructured":"Eppstein, D., Wortman, K.: Optimal angular resolution for face-symmetric drawings. Electronic preprint arxiv:0907.5474 (2009)"},{"key":"1_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1007\/978-3-642-03367-4_26","volume-title":"WADS 2009","author":"D. Eppstein","year":"2009","unstructured":"Eppstein, D., Wortman, K.: Optimal embedding into star metrics. In: Dehne, F., et al. (eds.) WADS 2009. LNCS, vol.\u00a05664, pp. 290\u2013301. Springer, Heidelberg (2009)"},{"key":"1_CR34","doi-asserted-by":"crossref","unstructured":"Evans, F., Skiena, S.S., Varshney, A.: Optimizing triangle strips for fast rendering. In: Proc. 7th IEEE Conf. Visualization, pp. 319\u2013326 (1996)","DOI":"10.1109\/VISUAL.1996.568125"},{"issue":"1","key":"1_CR35","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/0734-189X(84)90139-7","volume":"28","author":"L. Ferrari","year":"1984","unstructured":"Ferrari, L., Sankar, P.V., Sklansky, J.: Minimal rectangular partitions of digitized blobs. Computer Vision, Graphics, and Image Processing\u00a028(1), 58\u201371 (1984)","journal-title":"Computer Vision, Graphics, and Image Processing"},{"issue":"3","key":"1_CR36","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1016\/0095-8956(78)90059-X","volume":"24","author":"S. Fisk","year":"1978","unstructured":"Fisk, S.: A short proof of Chv\u00e1tal\u2019s watchman theorem. Journal of Combinatorial Theory, Series B\u00a024(3), 374 (1978)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"1_CR37","series-title":"Lecture Notes in Computer Science","volume-title":"WG 2009","author":"F. Fomin","year":"2009","unstructured":"Fomin, F., Lokshtanov, D., Saurabh, S.: An exact algorithm for minimum distortion embedding. In: Paul, C., Habib, M. (eds.) WG 2009. LNCS, vol.\u00a05911. Springer, Heidelberg (2009)"},{"key":"1_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/3-540-62495-3_49","volume-title":"Graph Drawing","author":"A. Garg","year":"1997","unstructured":"Garg, A., Tamassia, R.: A new minimum cost flow algorithm with applications to graph drawing. In: North, S.C. (ed.) GD 1996. LNCS, vol.\u00a01190, pp. 201\u2013216. Springer, Heidelberg (1997)"},{"key":"1_CR39","series-title":"Advances in Biochemical Engineering\/Biotechnology","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45713-5_1","volume-title":"Chip Technology","author":"S. Hannenhalli","year":"2002","unstructured":"Hannenhalli, S., Hubbell, E., Lipshutz, R., Pevzner, P.A.: Combinatorial algorithms for design of DNA arrays. In: Chip Technology. Advances in Biochemical Engineering\/Biotechnology, vol.\u00a077, pp. 1\u201319. Springer, Heidelberg (2002)"},{"issue":"3","key":"1_CR40","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1016\/0196-6774(91)90013-O","volume":"12","author":"J. Hershberger","year":"1991","unstructured":"Hershberger, J., Suri, S.: Finding tailored partitions. J. Algorithms\u00a012(3), 431\u2013463 (1991)","journal-title":"J. Algorithms"},{"issue":"4","key":"1_CR41","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An n5\/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput.\u00a02(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"key":"1_CR42","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1137\/0215033","volume":"15","author":"H. Imai","year":"1986","unstructured":"Imai, H., Asano, T.: Efficient algorithms for geometric graph search problems. SIAM J. Comput.\u00a015, 478\u2013494 (1986)","journal-title":"SIAM J. Comput."},{"key":"1_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/3-540-52921-7_52","volume-title":"Algorithms","author":"H. Imai","year":"1990","unstructured":"Imai, H., Iwano, K.: Efficient sequential and parallel algorithms for planar minimum cost flow. In: Asano, T., Imai, H., Ibaraki, T., Nishizeki, T. (eds.) SIGAL 1990. LNCS, vol.\u00a0450, pp. 21\u201330. Springer, Heidelberg (1990)"},{"key":"1_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-540-73545-8_13","volume-title":"Computing and Combinatorics","author":"K. Iwama","year":"2007","unstructured":"Iwama, K., Nakashima, T.: An improved exact algorithm for cubic graph TSP. In: Lin, G. (ed.) COCOON 2007. LNCS, vol.\u00a04598, pp. 108\u2013117. Springer, Heidelberg (2007)"},{"key":"1_CR45","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-18638-7","volume-title":"Graph Drawing Software","author":"M. Junger","year":"2004","unstructured":"Junger, M., Mutzel, P.: Graph Drawing Software. Springer, Heidelberg (2004)"},{"issue":"2","key":"1_CR46","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1137\/0604020","volume":"4","author":"J. Kahn","year":"1983","unstructured":"Kahn, J., Klawe, M., Kleitman, D.: Traditional galleries require fewer watchmen. SIAM Journal on Algebraic and Discrete Methods\u00a04(2), 194\u2013206 (1983)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"issue":"1","key":"1_CR47","doi-asserted-by":"crossref","first-page":"89","DOI":"10.37236\/178","volume":"16","author":"T. Kalinowski","year":"2009","unstructured":"Kalinowski, T.: A dual of the rectangle-segmentation problem for binary matrices. Electronic J. Combinatorics\u00a016(1), R89 (2009)","journal-title":"Electronic J. Combinatorics"},{"key":"1_CR48","unstructured":"Karp, R.M., Orlin, J.B.: Parametric Shortest Path Algorithms with an Application to Cyclic Staffing. Technical Report OR 103-80, MIT Operations Research Center (1980)"},{"key":"1_CR49","first-page":"116","volume":"38","author":"D. K\u0151nig","year":"1931","unstructured":"K\u0151nig, D.: Gr\u00e1fok \u00e9s m\u00e1trixok. Matematikai \u00e9s Fizikai Lapok\u00a038, 116\u2013119 (1931)","journal-title":"Matematikai \u00e9s Fizikai Lapok"},{"key":"1_CR50","series-title":"Foundations of Computing Series","volume-title":"Complexity Issues in VLSI","author":"T. Leighton","year":"1983","unstructured":"Leighton, T.: Complexity Issues in VLSI. Foundations of Computing Series. MIT Press, Cambridge (1983)"},{"key":"1_CR51","doi-asserted-by":"crossref","unstructured":"Li, G., Zhang, H.: A rectangular partition algorithm for planar self-assembly. In: Proc. IEEE\/RSJ Int. Conf. Intelligent Robots and Systems, pp. 3213\u20133218 (2005)","DOI":"10.1109\/IROS.2005.1545324"},{"key":"1_CR52","doi-asserted-by":"crossref","unstructured":"Linial, N.: Finite metric spaces\u2013combinatorics, geometry and algorithms. In: Proc. International Congress of Mathematicians, Beijing, vol.\u00a03, pp. 573\u2013586 (2002)","DOI":"10.1145\/513400.513441"},{"key":"1_CR53","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1002\/net.3230130308","volume":"13","author":"W. Lipski Jr.","year":"1983","unstructured":"Lipski Jr., W.: Finding a Manhattan path and related problems. Networks\u00a013, 399\u2013409 (1983)","journal-title":"Networks"},{"key":"1_CR54","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0020-0190(84)90105-4","volume":"19","author":"W. Lipski Jr.","year":"1984","unstructured":"Lipski Jr., W.: An O(nlogn) Manhattan path algorithm. Information Processing Letters\u00a019, 99\u2013102 (1984)","journal-title":"Information Processing Letters"},{"key":"1_CR55","doi-asserted-by":"crossref","first-page":"245","DOI":"10.3233\/FI-1978-2116","volume":"2","author":"W. Lipski Jr.","year":"1979","unstructured":"Lipski Jr., W., Lodi, E., Luccio, F., Mugnai, C., Pagli, L.: On two-dimensional data organization II. Fundamenta Informaticae\u00a02, 245\u2013260 (1979)","journal-title":"Fundamenta Informaticae"},{"key":"1_CR56","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1137\/S0895480193242931","volume":"7","author":"S. Malitz","year":"1994","unstructured":"Malitz, S., Papakostas, A.: On the angular resolution of planar graphs. SIAM J. Discrete Mathematics\u00a07, 172\u2013183 (1994)","journal-title":"SIAM J. Discrete Mathematics"},{"issue":"5","key":"1_CR57","doi-asserted-by":"publisher","first-page":"1002","DOI":"10.1137\/S0097539789162997","volume":"24","author":"G. Miller","year":"1995","unstructured":"Miller, G.: Flow in planar graphs with multiple sources and sinks. SIAM J. Comput.\u00a024(5), 1002\u20131017 (1995)","journal-title":"SIAM J. Comput."},{"key":"1_CR58","unstructured":"Mumford, E.: Drawing Graphs for Cartographic Applications. PhD thesis, Technische Universiteit Eindhoven (2008)"},{"key":"1_CR59","doi-asserted-by":"crossref","DOI":"10.1142\/5648","volume-title":"Planar Graph Drawing","author":"T. Nishizeki","year":"2004","unstructured":"Nishizeki, T., Rahman, M.S.: Planar Graph Drawing. World Scientific, Singapore (2004)"},{"key":"1_CR60","unstructured":"Ohtsuki, T.: Minimum dissection of rectilinear regions. In: Proc. IEEE Int. Symp. Circuits and Systems, pp. 1210\u20131213 (1982)"},{"key":"1_CR61","volume-title":"Art Gallery Theorems and Algorithms","author":"J. O\u2019Rourke","year":"1987","unstructured":"O\u2019Rourke, J.: Art Gallery Theorems and Algorithms. Oxford University Press, Oxford (1987)"},{"issue":"3","key":"1_CR62","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0010-4485(77)90118-X","volume":"9","author":"K. Patel","year":"1977","unstructured":"Patel, K.: Computer-aided decomposition of geometric contours into standardized areas. Computer-Aided Design\u00a09(3), 199\u2013203 (1977)","journal-title":"Computer-Aided Design"},{"key":"1_CR63","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF02392606","volume":"15","author":"J.P.C. Petersen","year":"1891","unstructured":"Petersen, J.P.C.: Die theorie der regularen graphs. Acta Mathematica\u00a015, 193\u2013220 (1891)","journal-title":"Acta Mathematica"},{"issue":"2","key":"1_CR64","doi-asserted-by":"publisher","first-page":"292","DOI":"10.2307\/208794","volume":"24","author":"E. Raisz","year":"1934","unstructured":"Raisz, E.: The rectangular statistical cartogram. Geographical Review\u00a024(2), 292\u2013296 (1934)","journal-title":"Geographical Review"},{"key":"1_CR65","first-page":"491","volume-title":"Handbook of Computational Geometry","author":"J.-R. Sack","year":"1999","unstructured":"Sack, J.-R., Urrutia, J.: Polygon decomposition. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 491\u2013518. Elsevier, Amsterdam (1999)"},{"key":"1_CR66","unstructured":"Savage, C.: Parallel Algorithms for Graph Theoretic Problems. PhD thesis, University of Illinois, Urbana-Champaign (1977)"},{"key":"1_CR67","doi-asserted-by":"crossref","unstructured":"Shamos, M.I., Hoey, D.: Closest-point problems. In: Proc. 16th IEEE Symp. Foundations of Computer Science, pp. 151\u2013162 (1975)","DOI":"10.1109\/SFCS.1975.8"},{"key":"1_CR68","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1080\/14786448408627475","volume":"17","author":"P.G. Tait","year":"1884","unstructured":"Tait, P.G.: Listing\u2019s Topologie. Philosophical Magazine (5th ser.)\u00a017, 30\u201346 (1884)","journal-title":"Philosophical Magazine (5th ser.)"},{"issue":"3","key":"1_CR69","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1137\/0216030","volume":"16","author":"R. Tamassia","year":"1987","unstructured":"Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput.\u00a016(3), 421\u2013444 (1987)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1_CR70","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1112\/jlms\/s1-21.2.98","volume":"21","author":"W.T. Tutte","year":"1946","unstructured":"Tutte, W.T.: On Hamiltonian circuits. Journal of the London Mathematical Society (2nd ser.)\u00a021(2), 98\u2013101 (1946); Reprinted in Scientific Papers, vol. II, pp. 85\u201398","journal-title":"Journal of the London Mathematical Society (2nd ser.)"},{"issue":"6","key":"1_CR71","doi-asserted-by":"publisher","first-page":"1201","DOI":"10.1137\/0218080","volume":"18","author":"P.M. Vaidya","year":"1989","unstructured":"Vaidya, P.M.: Geometry helps in matching. SIAM J. Comput.\u00a018(6), 1201\u20131225 (1989)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1_CR72","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/j.comgeo.2006.06.002","volume":"37","author":"M. Kreveld van","year":"2007","unstructured":"van Kreveld, M., Speckmann, B.: On rectangular cartograms. Computational Geometry Theory and Applications\u00a037(3), 175\u2013187 (2007)","journal-title":"Computational Geometry Theory and Applications"},{"key":"1_CR73","doi-asserted-by":"crossref","unstructured":"Xiang, X., Held, M., Mitchell, J.S.B.: Fast and effective stripification of polygonal surface models. In: Proc. Symp. Interactive 3D Graphics, pp. 71\u201378 (1999)","DOI":"10.1145\/300523.300531"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11409-0_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T16:17:51Z","timestamp":1739463471000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11409-0_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642114083","9783642114090"],"references-count":73,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11409-0_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}