{"docId":2099,"paperId":2099,"url":"https:\/\/dmtcs.episciences.org\/2099","doi":"10.46298\/dmtcs.2099","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":103,"name":"Vol. 16 no. 3"}],"section":[{"sid":9,"title":"Graph Theory","description":[]}],"repositoryName":"Hal","repositoryIdentifier":"hal-01188913","repositoryVersion":1,"repositoryLink":"https:\/\/hal.archives-ouvertes.fr\/hal-01188913v1","dateSubmitted":"2012-05-10 00:00:00","dateAccepted":null,"datePublished":"2014-08-01 00:00:00","titles":{"en":"Genus distributions of cubic series-parallel graphs"},"authors":["Gross, Jonathan L.","Kotrb\u010d\u00edk, Michal","Sun, Timothy"],"abstracts":{"0":"Graph Theory","en":"We derive a quadratic-time algorithm for the genus distribution of any 3-regular, biconnected series-parallel graph, which we extend to any biconnected series-parallel graph of maximum degree at most 3. Since the biconnected components of every graph of treewidth 2 are series-parallel graphs, this yields, by use of bar-amalgamation, a quadratic-time algorithm for every graph of treewidth at most 2 and maximum degree at most 3."},"keywords":[["graph embedding"],["genus distribution"],["series-parallel graphs"],["bounded treewidth"],"[INFO.INFO-DM] Computer Science [cs]\/Discrete Mathematics [cs.DM]"]}