{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,27]],"date-time":"2024-09-27T20:40:10Z","timestamp":1727469610920},"reference-count":0,"publisher":"Journal of Graph Algorithms and Applications","issue":"6","license":[{"start":{"date-parts":[[2023,7,1]],"date-time":"2023-07-01T00:00:00Z","timestamp":1688169600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["JGAA"],"abstract":"<jats:p>Let $G$ be a connected planar (but not yet embedded) graph and \n$F$ a set of edges with ends in $V(G)$ and not belonging to $E(G)$. \nThe multiple edge insertion problem (MEI) asks for a drawing of $G+F$ with the\nminimum number of pairwise edge crossings, such that the subdrawing of $G$ is plane. \nA solution to this problem is known to approximate the crossing number of the graph $G+F$,\nbut unfortunately, finding an exact solution to MEI is NP-hard for general $F$.\nThe MEI problem is linear-time solvable for the special case of $|F|=1$ (SODA 01 and Algorithmica), \nand there is a polynomial-time solvable extension in which all edges of $F$ are incident to a common\nvertex which is newly introduced into $G$ (SODA 09). \nThe complexity for general $F$ but with constant $k=|F|$ was open, but algorithms\nboth with relative and absolute approximation guarantees have been presented (SODA 11, ICALP 11 and JoCO). \nWe present a fixed-parameter algorithm for the MEI problem in the case that $G$ is biconnected,\nwhich is extended to also cover the case of connected $G$ with cut vertices of bounded degree.\nThese are the first exact algorithms for the general MEI problem, and they run in time $O(|V(G)|)$ for any constant $k$.<\/jats:p>","DOI":"10.7155\/jgaa.00631","type":"journal-article","created":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T14:42:02Z","timestamp":1689345722000},"page":"489-522","source":"Crossref","is-referenced-by-count":0,"title":["Inserting Multiple Edges into a Planar Graph"],"prefix":"10.7155","volume":"27","author":[{"given":"Markus","family":"Chimani","sequence":"first","affiliation":[]},{"given":"Petr","family":"Hlin\u011bn\u00fd","sequence":"additional","affiliation":[]}],"member":"4175","published-online":{"date-parts":[[2023,7,1]]},"container-title":["Journal of Graph Algorithms and Applications"],"original-title":[],"link":[{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/download\/paper631\/2327","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/download\/paper631\/2327","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,27]],"date-time":"2024-09-27T20:09:40Z","timestamp":1727467780000},"score":1,"resource":{"primary":{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/view\/paper631"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,1]]},"references-count":0,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2023,7,1]]}},"URL":"https:\/\/doi.org\/10.7155\/jgaa.00631","relation":{},"ISSN":["1526-1719"],"issn-type":[{"type":"electronic","value":"1526-1719"}],"subject":[],"published":{"date-parts":[[2023,7,1]]}}}