Search results for "planar graphs"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Sergio Cabello, Bojan Mohar	Adding one edge to planar graphs makes crossing number hard.	Symposium on Computational Geometry	2010	DBLP DOI BibTeX RDF	NP-hard, graph drawing, planar graphs, graph embedding, crossing number, topological graph theory
3	MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx	Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth.	STOC	2010	DBLP DOI BibTeX RDF	Steiner forest, bounded-genus graphs, bounded-treewidth graphs, planar graphs, PTAS, series-parallel graphs
3	Glencora Borradaile, Philip N. Klein, Claire Mathieu	An O(n log n) approximation scheme for Steiner tree in planar graphs.	ACM Transactions on Algorithms	2009	DBLP DOI BibTeX RDF	planar graphs, Steiner tree, approximation scheme
3	Zhengbing Bian, Qian-Ping Gu	Computing Branch Decomposition of Large Planar Graphs.	WEA	2008	DBLP DOI BibTeX RDF	computational study, Graph algorithms, planar graphs, algorithm engineering, branch-decomposition
3	Piotr Indyk, Anastasios Sidiropoulos	Probabilistic embeddings of bounded genus graphs into planar graphs.	Symposium on Computational Geometry	2007	DBLP DOI BibTeX RDF	bounded genus graphs, probabilistic approximation, embeddings, planar graphs
3	Thomas P. Hayes, Juan Carlos Vera, Eric Vigoda	Randomly coloring planar graphs with fewer colors than the maximum degree.	STOC	2007	DBLP DOI BibTeX RDF	Markov chain Monte Carlo (MCMC), graph coloring, planar graphs, coupling
3	Seok-Hee Hong, Peter Eades	Drawing Planar Graphs Symmetrically, III: Oneconnected Planar Graphs.	Algorithmica	2006	DBLP DOI BibTeX RDF	Planar geometric automorphisms, Symmetry, Graph drawing, Planar graphs
3	Marcin Mucha, Piotr Sankowski	Maximum Matchings in Planar Graphs via Gaussian Elimination.	Algorithmica	2006	DBLP DOI BibTeX RDF	Planar graphs, Maximum matching, Fast matrix multiplication
3	Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd	Edge-disjoint paths in Planar graphs with constant congestion.	STOC	2006	DBLP DOI BibTeX RDF	Planar graphs, multicommodity flow, edge-disjoint paths
3	Seok-Hee Hong, Peter Eades	Drawing Planar Graphs Symmetrically, II: Biconnected Planar Graphs.	Algorithmica	2005	DBLP DOI BibTeX RDF	Symmetry, Graph drawing, Planar graphs, Graph automorphism
3	Zhi-Zhong Chen, Mitsuharu Kouno	A Linear-Time Algorithm for 7-Coloring 1-Plane Graphs.	Algorithmica	2005	DBLP DOI BibTeX RDF	Plane embeddings, Plane embeddings, NP-completeness, Graph algorithms, Planar graphs, Planar graphs, Vertex coloring
3	Carlo Gaibisso, Guido Proietti, Richard B. Tan	Optimal MST Maintenance for Transient Deletion of Every Node in Planar Graphs.	COCOON	2003	DBLP DOI BibTeX RDF	Transient Node Failures, Radio Networks Survivability, Planar Graphs, Minimum Spanning Tree
3	Tiziana Calamoneri, Rossella Petreschi	L(2, 1)-labeling of planar graphs.	DIAL-M	2001	DBLP DOI BibTeX RDF	L(2, 1)-labeling, planar graphs, outerplanar graphs, multi-hop radio networks
3	J. Ian Munro, Venkatesh Raman	Succinct Representation of Balanced Parentheses, Static Trees and Planar Graphs.	FOCS	1997	DBLP DOI BibTeX RDF	balanced parentheses, static trees, rooted ordered tree, planar graphs, abstract data types, abstract data types, binary tree, adjacency, succinct representation
3	Daniel A. Spielman, Shang-Hua Teng	Spectral Partitioning Works: Planar Graphs and Finite Element Meshes.	FOCS	1996	DBLP DOI BibTeX RDF	bounded-degree planar graphs, planar graphs, finite element analysis, numerical algorithms, spectral partitioning, finite element meshes
3	Philip N. Klein, Sairam Subramanian	A linear-processor polylog-time algorithm for shortest paths in planar graphs	FOCS	1993	DBLP DOI BibTeX RDF	linear-processor polylog-time algorithm, directed planar graphs, bounded-genus graphs, 2-dimensional overlap graphs, shortest paths, planar graphs, separators, decomposition tree
3	Goos Kant	Drawing Planar Graphs Using the lmc-Ordering (Extended Abstract)	FOCS	1992	DBLP DOI BibTeX RDF	visibility representations, lmc-ordering, required area, minimum angle, number of bends, planar drawings, triconnected planar graphs, planar graphs, faces, vertices
3	Martin Fürer	Contracting Planar Graphs Efficiency in Parallel.	FSTTCS	1991	DBLP DOI BibTeX RDF	Additional Keywords and Phrases Planar graphs, Fáry embeddings, Parallel algorithms
2	Stefan Felsner, Mathew C. Francis	Contact representations of planar graphs with cubes.	Symposium on Computational Geometry	2011	DBLP DOI BibTeX RDF
2	Mohammad Khairul Hasan, Sung-Eui Yoon, Kyung-Yong Chwa	Bounds on the Geometric Mean of Arc Lengths for Bounded-Degree Planar Graphs.	FAW	2009	DBLP DOI BibTeX RDF
2	Haim Kaplan, Yahav Nussbaum	Maximum Flow in Directed Planar Graphs with Vertex Capacities.	ESA	2009	DBLP DOI BibTeX RDF
2	Omid Amini, Louis Esperet, Jan van den Heuvel	A unified approach to distance-two colouring of planar graphs.	SODA	2009	DBLP BibTeX RDF
2	Yusuke Kobayashi, Ken-ichi Kawarabayashi	Algorithms for finding an induced cycle in planar graphs and bounded genus graphs.	SODA	2009	DBLP BibTeX RDF
2	Konstantinos Panagiotou, Angelika Steger	Maximal biconnected subgraphs of random planar graphs.	SODA	2009	DBLP BibTeX RDF
2	Erik D. Demaine, MohammadTaghi Hajiaghayi, Philip N. Klein	Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs.	ICALP	2009	DBLP DOI BibTeX RDF
2	Mahdieh Hasheminezhad, Brendan D. McKay, Tristan Reeves	Recursive Generation of 5-Regular Planar Graphs.	WALCOM	2009	DBLP DOI BibTeX RDF	pentangulation, quintic, 5-regular, 5-valent, graph, map, planar
2	Baoyindureng Wu, Xinhui An	A Note on Edge Choosability and Degeneracy of Planar Graphs.	COCOA	2009	DBLP DOI BibTeX RDF	Planar graphs, List coloring
2	Ashkan Aazami, Joseph Cheriyan, Krishnam Raju Jampani	Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
2	Qian-Ping Gu, Hisao Tamaki	Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n1 + ε) Time.	ISAAC	2009	DBLP DOI BibTeX RDF	Graph algorithms, graph minors, branch-decompositions
2	Craig Dillabaugh, Meng He, Anil Maheshwari, Norbert Zeh	I/O and Space-Efficient Path Traversal in Planar Graphs.	ISAAC	2009	DBLP DOI BibTeX RDF
2	Robert Franke, Ignaz Rutter, Dorothea Wagner	Computing Large Matchings in Planar Graphs with Fixed Minimum Degree.	ISAAC	2009	DBLP DOI BibTeX RDF
2	Glencora Borradaile, James R. Lee, Anastasios Sidiropoulos	Randomly removing g handles at once.	Symposium on Computational Geometry	2009	DBLP DOI BibTeX RDF	bounded genus graphs, probabilistic approximation, embeddings, planar graphs
2	Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy	Planar and Grid Graph Reachability Problems.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Logspace, Algorithms, Planar graphs, Reachability, Complexity theory, Circuit complexity, Grid graphs
2	Richard Cole, Lukasz Kowalik	New Linear-Time Algorithms for Edge-Coloring Planar Graphs.	Algorithmica	2008	DBLP DOI BibTeX RDF	Algorithm, Planar graph, Edge-coloring, Linear-time
2	Qian-Ping Gu, Hisao Tamaki	Optimal branch-decomposition of planar graphs in O(n3) Time.	ACM Transactions on Algorithms	2008	DBLP DOI BibTeX RDF	planar graphs, Branch-decompositions
2	Nicolas Nisse, Karol Suchan	Fast Robber in Planar Graphs.	WG	2008	DBLP DOI BibTeX RDF	Cops and robber, grid, planar graph, subdivision, minor
2	J. Joseph Fowler, Michael Jünger, Stephen G. Kobourov, Michael Schulz	Characterizations of Restricted Pairs of Planar Graphs Allowing Simultaneous Embedding with Fixed Edges.	WG	2008	DBLP DOI BibTeX RDF
2	Sadish Sadasivam, Huaming Zhang	On Representation of Planar Graphs by Segments.	AAIM	2008	DBLP DOI BibTeX RDF
2	Glencora Borradaile, Philip N. Klein	The Two-Edge Connectivity Survivable Network Problem in Planar Graphs.	ICALP	2008	DBLP DOI BibTeX RDF
2	Vladimir E. Alekseev, Vadim V. Lozin, Dmitriy S. Malyshev, Martin Milanic	The Maximum Independent Set Problem in Planar Graphs.	MFCS	2008	DBLP DOI BibTeX RDF	maximum independent set problem, hereditary classes, planar graphs
2	Christoph Lenzen, Yvonne Anne Oswald, Roger Wattenhofer	What can be approximated locally?: case study: dominating sets in planar graphs.	SPAA	2008	DBLP DOI BibTeX RDF	distributed algorithms, approximation, planar graphs, local algorithms, dominating sets
2	Marjan Marzban, Qian-Ping Gu, Xiaohua Jia	Computational Study on Dominating Set Problem of Planar Graphs.	COCOA	2008	DBLP DOI BibTeX RDF	PLANAR DOMINATING SET, computational study, data reduction, fixed-parameter algorithms, branch-decomposition
2	Hans L. Bodlaender, Eelko Penninkx, Richard B. Tan	A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs.	ISAAC	2008	DBLP DOI BibTeX RDF
2	Sergio Cabello, Bojan Mohar	Crossing and Weighted Crossing Number of Near-Planar Graphs.	Graph Drawing	2008	DBLP DOI BibTeX RDF
2	Ioannis Koutis, Gary L. Miller	Graph partitioning into isolated, high conductance clusters: theory, computation and applications to preconditioning.	SPAA	2008	DBLP DOI BibTeX RDF	combinatorial preconditioning, multi-way decompositions, planar graphs, spectral graph theory
2	Stefan Felsner, Florian Zickfeld	Schnyder Woods and Orthogonal Surfaces.	Discrete & Computational Geometry	2008	DBLP DOI BibTeX RDF	Schnyder woods, Orthogonal surfaces, Graph drawing, Planar graphs, Order dimension
2	Hannes Moser, Somnath Sikdar	The Parameterized Complexity of the Induced Matching Problem in Planar Graphs.	FAW	2007	DBLP DOI BibTeX RDF
2	Cyril Gavoille, Arnaud Labourel	Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs.	ESA	2007	DBLP DOI BibTeX RDF
2	Laurent Flindt Muller, Martin Zachariasen	Fast and Compact Oracles for Approximate Distances in Planar Graphs.	ESA	2007	DBLP DOI BibTeX RDF
2	Glencora Borradaile, Claire Kenyon-Mathieu, Philip N. Klein	A polynomial-time approximation scheme for Steiner tree in planar graphs.	SODA	2007	DBLP BibTeX RDF
2	André Berger, Michelangelo Grigni	Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs.	ICALP	2007	DBLP DOI BibTeX RDF
2	Jiong Guo, Rolf Niedermeier	Linear Problem Kernels for NP-Hard Problems on Planar Graphs.	ICALP	2007	DBLP DOI BibTeX RDF
2	Mingji Xia	Maximum Edge-Disjoint Paths Problem in Planar Graphs.	TAMC	2007	DBLP DOI BibTeX RDF	maximum edge-disjoint paths, #P-hard, determinant
2	James R. Lee, Prasad Raghavendra	Coarse Differentiation and Multi-flows in Planar Graphs.	APPROX-RANDOM	2007	DBLP DOI BibTeX RDF
2	Muhammad Rezaul Karim 0001, Md. Saidur Rahman 0001	Straight-line grid drawings of planar graphs with linear area.	APVIS	2007	DBLP DOI BibTeX RDF
2	Emilio Di Giacomo, Walter Didimo, Marc J. van Kreveld, Giuseppe Liotta, Bettina Speckmann	Matched Drawings of Planar Graphs.	Graph Drawing	2007	DBLP DOI BibTeX RDF
2	Fabrizio Frati, Maurizio Patrignani	A Note on Minimum-Area Straight-Line Drawings of Planar Graphs.	Graph Drawing	2007	DBLP DOI BibTeX RDF
2	Hazel Everett, Sylvain Lazard, Giuseppe Liotta, Stephen K. Wismath	Universal Sets of n Points for 1-Bend Drawings of Planar Graphs with n Vertices.	Graph Drawing	2007	DBLP DOI BibTeX RDF
2	J. Joseph Fowler, Stephen G. Kobourov	Characterization of Unlabeled Level Planar Graphs.	Graph Drawing	2007	DBLP DOI BibTeX RDF
2	Mark Braverman, Raghav Kulkarni, Sambuddha Roy	Parity Problems in Planar Graphs.	IEEE Conference on Computational Complexity	2007	DBLP DOI BibTeX RDF
2	Ashkan Aazami, Michael D. Stilp	Approximation Algorithms and Hardness for Domination with Propagation.	APPROX-RANDOM	2007	DBLP DOI BibTeX RDF	Power Dominating Set, Approximation Algorithms, Integer Programming, Planar Graphs, Greedy Algorithms, Dominating Set, Hardness of Approximation, PTAS
2	Bruno Escoffier, Laurent Gourvès, Jérôme Monnot	Complexity and Approximation Results for the Connected Vertex Cover Problem.	WG	2007	DBLP DOI BibTeX RDF	Connected vertex cover, APX-complete, approximation algorithm, planar graphs, bipartite graphs, chordal graphs
2	Lukasz Kowalik, Maciej Kurowski	Oracles for bounded-length shortest paths in planar graphs.	ACM Transactions on Algorithms	2006	DBLP DOI BibTeX RDF	Bounded length, shortest path, planar graph, dynamic environment, oracle
2	Mohammad R. Salavatipour	Large Induced Forests in Triangle-Free Planar Graphs.	Graphs and Combinatorics	2006	DBLP DOI BibTeX RDF
2	Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Dominique Poulalhon, Gilles Schaeffer	Planar Graphs, via Well-Orderly Maps and Trees.	Graphs and Combinatorics	2006	DBLP DOI BibTeX RDF	Well-orderly, Triangulation, Planar graph, Realizer
2	Seok-Hee Hong, Brendan D. McKay, Peter Eades	A Linear Time Algorithm for Constructing Maximally Symmetric Straight Line Drawings of Triconnected Planar Graphs.	Discrete & Computational Geometry	2006	DBLP DOI BibTeX RDF
2	Lyudmil Aleksandrov, Hristo Djidjev, Hua Guo, Anil Maheshwari	Partitioning planar graphs with costs and weights.	ACM Journal of Experimental Algorithmics	2006	DBLP DOI BibTeX RDF	graph partitioning algorithms, implementation, Graph algorithms, graph separators
2	Tobias Storch	How randomized search heuristics find maximum cliques in planar graphs.	GECCO	2006	DBLP DOI BibTeX RDF
2	Milovan Suvakov, Bosiljka Tadic	Topology of Cell-Aggregated Planar Graphs.	International Conference on Computational Science	2006	DBLP DOI BibTeX RDF
2	Herman J. Haverkort, Laura Toma	I/O-Efficient Algorithms on Near-Planar Graphs.	LATIN	2006	DBLP DOI BibTeX RDF
2	Petr Hlinený, Gelasio Salazar	On the Crossing Number of Almost Planar Graphs.	Graph Drawing	2006	DBLP DOI BibTeX RDF	crossing-critical graphs, planarization, crossing number, crossing minimization
2	Andrzej Czygrinow, Michal Hanckowiak, Edyta Szymanska	Distributed Approximation Algorithms for Planar Graphs.	CIAC	2006	DBLP DOI BibTeX RDF
2	MohammadHossein Bateni, Mohammad Taghi Hajiaghayi, Erik D. Demaine, Mohammad Moharrami	Plane embeddings of planar graph metrics.	Symposium on Computational Geometry	2006	DBLP DOI BibTeX RDF	planar graphs, metric embedding, Euclidean plane
2	Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos	Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs.	ACM Transactions on Algorithms	2005	DBLP DOI BibTeX RDF	(k, r)-center, planar graph, domination, fixed-parameter algorithms, map graph
2	Therese C. Biedl, Dana F. Wilkinson	Bounded-Degree Independent Sets in Planar Graphs.	Theory Comput. Syst.	2005	DBLP DOI BibTeX RDF
2	Van Bang Le, Raffaele Mosca, Haiko Müller	On Stable Cutsets in Claw-Free Graphs and Planar Graphs.	WG	2005	DBLP DOI BibTeX RDF
2	André Berger, Artur Czumaj, Michelangelo Grigni, Hairong Zhao	Approximation Schemes for Minimum 2-Connected Spanning Subgraphs in Weighted Planar Graphs.	ESA	2005	DBLP DOI BibTeX RDF
2	Frederic Dorn, Eelko Penninkx, Hans L. Bodlaender, Fedor V. Fomin	Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions.	ESA	2005	DBLP DOI BibTeX RDF
2	Stefanie Gerke, Colin McDiarmid, Angelika Steger, Andreas Weißl	Random planar graphs with n nodes and a fixed number of edges.	SODA	2005	DBLP BibTeX RDF
2	Narong Punnim	The Decycling Number of Cubic Planar Graphs.	CJCDGCGT	2005	DBLP DOI BibTeX RDF
2	Jon M. Kleinberg	An Approximation Algorithm for the Disjoint Paths Problem in Even-Degree Planar Graphs.	FOCS	2005	DBLP DOI BibTeX RDF
2	Manuel Bodirsky, Clemens Gröpl, Mihyun Kang	Sampling Unlabeled Biconnected Planar Graphs.	ISAAC	2005	DBLP DOI BibTeX RDF
2	Leszek Gasieniec, David Peleg, Qin Xin	Faster communication in known topology radio networks.	PODC	2005	DBLP DOI BibTeX RDF	algorithms, broadcasting, planar graphs, gossiping, radio networks
2	Sabeel Ansari, Lata Narayanan, Jaroslav Opatrny	A Generalization of the Face Routing.	MobiQuitous	2005	DBLP DOI BibTeX RDF	crossing edges, ad hoc networks, Wireless networks, MANET, routing algorithms, planar graphs, geometric graphs, position-based routing
2	Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Dominique Poulalhon, Gilles Schaeffer	Planar Graphs, via Well-Orderly Maps and Trees.	WG	2004	DBLP DOI BibTeX RDF
2	Lukasz Kowalik	Fast 3-Coloring Triangle-Free Planar Graphs.	ESA	2004	DBLP DOI BibTeX RDF
2	Marcin Mucha, Piotr Sankowski	Maximum Matchings in Planar Graphs via Gaussian Elimination.	ESA	2004	DBLP DOI BibTeX RDF
2	Artur Czumaj, Michelangelo Grigni, Papa Sissokho, Hairong Zhao	Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs.	SODA	2004	DBLP BibTeX RDF
2	Parinya Chalermsook, Jittat Fakcharoenphol, Danupon Nanongkai	A deterministic near-linear time algorithm for finding minimum cuts in planar graphs.	SODA	2004	DBLP BibTeX RDF
2	Cesim Erten, Stephen G. Kobourov, Chandan Pitta	Morphing planar graphs.	Symposium on Computational Geometry	2004	DBLP DOI BibTeX RDF	graph drawing, planar graphs, morphing
2	Fedor V. Fomin, Dimitrios M. Thilikos	A Simple and Fast Approach for Solving Problems on Planar Graphs.	STACS	2004	DBLP DOI BibTeX RDF
2	Michel Neuhaus, Horst Bunke	An Error-Tolerant Approximate Matching Algorithm for Attributed Planar Graphs and Its Application to Fingerprint Classification.	SSPR/SPR	2004	DBLP DOI BibTeX RDF
2	Dániel Marx	Minimum Sum Multicoloring on the Edges of Planar Graphs and Partial k-Trees.	WAOA	2004	DBLP DOI BibTeX RDF
2	Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd	Edge-Disjoint Paths in Planar Graphs.	FOCS	2004	DBLP DOI BibTeX RDF
2	Seok-Hee Hong, Peter Eades	A Linear Time Algorithm for Constructing Maximally Symmetric Straight-Line Drawings of Planar Graphs.	Graph Drawing	2004	DBLP DOI BibTeX RDF
2	Cesim Erten, Stephen G. Kobourov	Simultaneous Embedding of Planar Graphs with Few Bends.	Graph Drawing	2004	DBLP DOI BibTeX RDF
2	Danny Z. Chen, Xiaodong Wu	Efficient Algorithms for k-Terminal Cuts on Planar Graphs.	Algorithmica	2003	DBLP DOI BibTeX RDF
2	Stefan Felsner	Geodesic Embeddings and Planar Graphs.	Order	2003	DBLP DOI BibTeX RDF	Schnyder labeling, orthogonal surface, graph drawing, order dimension
2	Lukasz Kowalik	Short Cycles in Planar Graphs.	WG	2003	DBLP DOI BibTeX RDF
2	Paul S. Bonsma	The Complexity of the Matching-Cut Problem for Planar Graphs and Other Graph Classes.	WG	2003	DBLP DOI BibTeX RDF