{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:17:09Z","timestamp":1759637829314},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540637578"},{"type":"electronic","value":"9783540696438"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0024490","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T02:30:56Z","timestamp":1132367456000},"page":"85-99","source":"Crossref","is-referenced-by-count":4,"title":["NP-completeness results for minimum planar spanners"],"prefix":"10.1007","author":[{"given":"Ulrik","family":"Brandes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dagmar","family":"Handke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I. Alth\u00f6fer","year":"1993","unstructured":"Ingo Alth\u00f6fer, Gautam Das, David Dobkin, Deborah Joseph, and Jos\u00e9 Soares. On sparse spanners of weighted graphs. Discrete Comput. Geom., 9:81\u2013100, 1993.","journal-title":"Discrete Comput. Geom."},{"key":"9_CR2","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 planarity using PQ-tree algorithms. J. of Computer and System Sciences, 13:335\u2013379, 1976.","journal-title":"J. of Computer and System Sciences"},{"key":"9_CR3","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0166-218X(94)90073-6","volume":"48","author":"L. Cai","year":"1994","unstructured":"Leizhen Cai. NP-completeness of minimum spanner problems. Discrete Applied Math., 48:187\u2013194, 1994.","journal-title":"Discrete Applied Math."},{"issue":"3","key":"9_CR4","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S0895480192237403","volume":"8","author":"L. Cai","year":"1995","unstructured":"Leizhen Cai and D.G. Corneil. Tree spanners. SIAM J. Discrete Math., 8(3):359\u2013387, 1995.","journal-title":"SIAM J. Discrete Math."},{"key":"9_CR5","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. E. Hopcroft","year":"1974","unstructured":"John E. Hopcroft and Robert E. Tarjan. Efficient planarity testing. J. of the Association for Computing Machinery, 21:549\u2013568, 1974.","journal-title":"J. of the Association for Computing Machinery"},{"key":"9_CR6","first-page":"305","volume":"22","author":"S.L. Hakimi","year":"1964","unstructured":"S.L. Hakimi and S.-T. Yau. Distance matrix of a graph and its realizability. Q. J. Mech. appl. Math., 22:305\u2013317, 1964.","journal-title":"Q. J. Mech. appl. Math."},{"key":"9_CR7","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1002\/net.3230230206","volume":"23","author":"A.L. Liestman","year":"1993","unstructured":"A.L. Liestman and Thomas Shermer. Grid spanners. Networks, 23:123\u2013133, 1993.","journal-title":"Networks"},{"key":"9_CR8","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1017\/S030500410006028X","volume":"93","author":"A. Mansfield","year":"1983","unstructured":"Anthony Mansfield. Determining the thickness of graphs is NP-hard. Math. Proc. Camb. Phil. Soc., 93:9\u201323, 1983.","journal-title":"Math. Proc. Camb. Phil. Soc."},{"key":"9_CR9","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"David Peleg and Alejandro A. Sch\u00e4ffer. Graph spanners. J. of Graph Theory, 13:99\u2013116, 1989.","journal-title":"J. of Graph Theory"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"David Peleg and Jeffrey D. Ullman. An optimal synchronizer for the hypercube. In Proceedings 1987 6th ACM Symposium on Principles of Dist. Comp., Vancouver, pages 77\u201385, 1987.","DOI":"10.1145\/41840.41847"},{"key":"9_CR11","first-page":"225","volume":"89","author":"J. Soares","year":"1992","unstructured":"Jos\u00e9 Soares. Graph spanners: a survey. Congressus Numerantium, 89:225\u2013238, 1992.","journal-title":"Congressus Numerantium"}],"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\/BFb0024490","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,4]],"date-time":"2019-02-04T18:10:15Z","timestamp":1549303815000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0024490"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540637578","9783540696438"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/bfb0024490","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}