[{"conference":{"name":"Graph Drawing and Network Visualization","start_date":"2018-09-26","location":"Barcelona, Spain","end_date":"2018-09-28"},"language":[{}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1808.07608"}],"external_id":{"arxiv":[],"isi":[]},"oa":1,"isi":1,"quality_controlled":"1","publication_identifier":{"isbn":[]},"month":"12","author":[{"first_name":"Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774"},{"first_name":"Csaba D.","last_name":"Tóth"}],"volume":"11282 ","date_created":"2018-12-30T22:59:15Z","dini_type":"doc-type:conferenceObject","date_updated":"2023-09-11T12:49:55Z","department":[{"_id":"UlWa","tree":[{"_id":"ResearchGroups"},{"_id":"IST"}]}],"publication_status":"published","creator":{"id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","login":"apreinsp"},"date_published":"2018-12-18T00:00:00Z","citation":{"apa":"Fulek, R., & Tóth, C. D. (2018). Crossing minimization in perturbed drawings (Vol. 11282, pp. 229–241). Presented at the Graph Drawing and Network Visualization, Barcelona, Spain: Springer. https://doi.org/10.1007/978-3-030-04414-5_16","ieee":"R. Fulek and C. D. Tóth, “Crossing minimization in perturbed drawings,” presented at the Graph Drawing and Network Visualization, Barcelona, Spain, 2018, vol. 11282, pp. 229–241.","ista":"Fulek R, Tóth CD. 2018. Crossing minimization in perturbed drawings. Graph Drawing and Network Visualization, LNCS, vol. 11282, 229–241.","short":"R. Fulek, C.D. Tóth, in:, Springer, 2018, pp. 229–241.","mla":"Fulek, Radoslav, and Csaba D. Tóth. Crossing Minimization in Perturbed Drawings. Vol. 11282, Springer, 2018, pp. 229–41, doi:10.1007/978-3-030-04414-5_16.","chicago":"Fulek, Radoslav, and Csaba D. Tóth. “Crossing Minimization in Perturbed Drawings,” 11282:229–41. Springer, 2018. https://doi.org/10.1007/978-3-030-04414-5_16."},"page":"229-241","uri_base":"https://research-explorer.ista.ac.at","article_processing_charge":"No","day":"18","dc":{"rights":["info:eu-repo/semantics/openAccess"],"source":["Fulek R, Tóth CD. Crossing minimization in perturbed drawings. In: Vol 11282. Springer; 2018:229-241. doi:10.1007/978-3-030-04414-5_16"],"title":["Crossing minimization in perturbed drawings","LNCS"],"relation":["info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-030-04414-5_16","info:eu-repo/semantics/altIdentifier/isbn/9783030044138","info:eu-repo/semantics/altIdentifier/wos/000672802500016","info:eu-repo/semantics/altIdentifier/arxiv/1808.07608"],"publisher":["Springer"],"date":["2018"],"language":["eng"],"identifier":["https://research-explorer.ista.ac.at/record/5791"],"type":["info:eu-repo/semantics/conferenceObject","doc-type:conferenceObject","text","http://purl.org/coar/resource_type/c_5794"],"description":["Due to data compression or low resolution, nearby vertices and edges of a graph drawing may be bundled to a common node or arc. We model such a “compromised” drawing by a piecewise linear map φ:G → ℝ. We wish to perturb φ by an arbitrarily small ε>0 into a proper drawing (in which the vertices are distinct points, any two edges intersect in finitely many points, and no three edges have a common interior point) that minimizes the number of crossings. An ε-perturbation, for every ε>0, is given by a piecewise linear map (Formula Presented), where with ||·|| is the uniform norm (i.e., sup norm). We present a polynomial-time solution for this optimization problem when G is a cycle and the map φ has no spurs (i.e., no two adjacent edges are mapped to overlapping arcs). We also show that the problem becomes NP-complete (i) when G is an arbitrary graph and φ has no spurs, and (ii) when φ may have spurs and G is a cycle or a union of disjoint paths."],"creator":["Fulek, Radoslav","Tóth, Csaba D."]},"scopus_import":"1","oa_version":"Preprint","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"5791","status":"public","abstract":[{"lang":"eng"}],"type":"conference","alternative_title":[]}]