{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:56:24Z","timestamp":1750308984473,"version":"3.41.0"},"reference-count":0,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[1984,1,1]],"date-time":"1984-01-01T00:00:00Z","timestamp":441763200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[1984,1]]},"abstract":"<jats:p>This paper addresses a class of graph embeding problems in which the object is to map the vertices of one graph to the vertices of another, so that the images of vertices that are adjacent in the &lt;u&gt;source graph&lt;\/u&gt; are close together in the &lt;u&gt;target graph.&lt;\/u&gt; An important special case is the bandwidth minimization problem in which the target graph is a simple line graph. In a previous paper, this author showed that for random graphs having bandwidth at most &lt;u&gt;k&lt;\/u&gt;, a well-known heuristic produces solutions having cost not more than 3&lt;u&gt;k&lt;\/u&gt; with high probability. This paper ger ralizes these results to the general graph embedding problem. A class of heuristics is described that can be applied to many families of target graphs. Certain aspects of these heuristics depend on properties of the target graphs. These properties are characterized and used to state several metatheorems. Typical of the results is a theorem showing that there exists an efficient heuristic that for random graphs having a cost &lt;u&gt;k&lt;\/u&gt; embedding in a rectangular grid, will produce an embedding having cost not more than 3&lt;u&gt;k&lt;\/u&gt; with high probability.<\/jats:p>","DOI":"10.1145\/1008939.1008943","type":"journal-article","created":{"date-parts":[[2004,10,12]],"date-time":"2004-10-12T15:20:46Z","timestamp":1097594446000},"page":"59-59","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["On the general graph embedding problem with applications to circuit layout"],"prefix":"10.1145","volume":"15","author":[{"given":"Jonathan S.","family":"Turner","sequence":"first","affiliation":[{"name":"Washington University, St. Louis, Missouri"}]}],"member":"320","published-online":{"date-parts":[[1984,1]]},"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1008939.1008943","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1008939.1008943","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:41:08Z","timestamp":1750282868000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1008939.1008943"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984,1]]},"references-count":0,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1984,1]]}},"alternative-id":["10.1145\/1008939.1008943"],"URL":"https:\/\/doi.org\/10.1145\/1008939.1008943","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[1984,1]]},"assertion":[{"value":"1984-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}