Note: The references are not ordered alphabetically!
1600 
D. Eppstein Recognizing partial cubes in quadratic time Journal of Graph Algorithms and Applications Vol.15 No.2 269293 (2011) JGAA 
1601 
S. Ovchinnikov Graphs and cubes Universitext, Springer 2011 
1602 
W. Imrich, S. Klavzar A simple O(mn) algorithm for recognizing Hamming graphs Bull. Inst. Combin. Appl. 9 4556 (1993) 
1603 
P. Winkler Isometric embeddings in products of complete graphs Discrete Appl. Math. 7 221225 (1984) 
1604 
W. Imrich, S. Klavzar Recognizing Hamming graphs in linear time and space Information Proc. Lett. 63 No.2 9195 (1997) 
1605 
H.J. Bandelt, V. Chepoi Metric graph theory and geometry: a survey Contemporary Mathematics 453 4986 (2008) 
1606 
W. Imrich, S. Klavzar, H.M. Mulder Median graphs and trianglefree graphs SIAM J. Discrete Math. 12 111118 (1999) doi 10.1137/S0895480197323494 
1607 
W. Imrich, S. Klavzar A Convexity Lemma and Expansion Procedures for Bipartite Graphs European J. Combin. 19 No.6 677685 (1998) Note that there is an error in this article, see
[1608]
.
B. Bresar, W. Imrich, S. Klavzar
Fast recognition algorithms for classes of partial cubes Discrete Appl. Math. 131 No.1 5161 (2003) 
1608 
B. Bresar, W. Imrich, S. Klavzar Fast recognition algorithms for classes of partial cubes Discrete Appl. Math. 131 No.1 5161 (2003) doi 10.1016/S0166218X(02)00416X 
1609 
Y. Otachi, Y. Okamoto, K. Yamazaki Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs Discrete Appl. Math. 155 No.17 23832390 (2007) doi 10.1016/j.dam.2007.07.010 
1610 
A. Brandstaedt, F.F. Dragan, E. Koehler Linear time algorithms for the Hamiltonian problems on (claw,net)free graphs SIAM J. Computing 30 16621677 (2000) 
1611 
D. Krumme, K. Venkataraman, G. Cybenko Hypercube embedding is NPcomplete In Heath, M., editor, Hypercube Microprocessors SIAM, Philadelphia (1986) 
1612 
F. Harary Cubical graphs and cubical dimensions Computers & Mathematics with Applications No.15 271–275 (1988) 
1613 
F. Harary, J.P. Hayes, H.J. Wu A survey of the theory of hypercube graphs Computers & Mathematics with Applications No.15 277–289 (1988) 
1614 
F. Afrati, C.H. Papadimitriou, G. Papageorgiou The complexity of cubical graphs Information and control 66 5360 (1985) 
1615 
I. Havel, J. Moravek Bvaluations of graphs Czech. Math. J. 22 338352 (1972) 
1616 
D. Goncalves, A. Pinlou, M. Rao, S. Thomasse The domination number of grids SIAM J. Discrete Math. 25 No.3 14431453 (2011) 
1617 
W.T. Trotter Jr. A Characterization of Roberts' Inequality for Boxicity Discrete Math. 28 303313 (1979) 
1618 
T.M. Chan A note on maximum independent sets in rectangle intersection graphs Inform. Proc. Lett. 89 1923 (2004) 
1619 
L. Alcón, L. Faria, C.M.H. de Figueiredo, M. Gutierrez The complexity of clique graph recognition Theoret. Comput. Sci. 410 20722083 (2009) doi 10.1016/j.tcs.2009.01.018 
1620 
Ki. Kawarabayashi Planarity allowing few error vertices in linear time Proc. 50th IEEE Symposium on Foundations of Computer Science (FOCS '09) 639648 (2009) doi 10.1109/FOCS.2009.45 
1621 
B. Mohar Face covers and the genus problem for apex graphs J. Combin. Theory (B), 82(1) 102117 (2000) doi 10.1006/jctb.2000.2026 
1622 
D. Bienstock, C.L. Monma On the complexity of embedding planar graphs to minimize certain distance measures Algorithmica 5 92109 (1990) 
1623 
F. Harary, C. Holtzmann Line graphs of bipartite graphs Rev. Soc. Mat. Chile 1 1922 (1974) 
1624  A.E. Brouwer Strongly regular graphs 
1625 
P.J. Cameron Strongly regular graphs in: Topics in Algebraic Graph Theory, L.W. Beineke and R.J. Wilson eds., Cambridge University Press 203221 (2004) 
1626 
A.E. Brouwer Classification of small (0,2)graphs J. Combin. Th. (A) 113 16361645 (2006) 
1627 
N.B. Limaye, D.G. Sarvate, P. Stanica, P.T. Young Regular and strongly regular planar graphs J. Comb. Math. Comb. Comput. 54 111127 (2005) 
1628 
J. Diaz, M. Karminski MaxCut and MaxBisection are NPhard on unit disk graphs Theo. Comp. Sci 377 271276 (2007) 
1629 
H.L. Bodlaender, K. Jansen On the complexity of the maximum cut problem Nordic J. Comput. 7 No.1 1431 (2000) 
1630 
M. Yannakakis Node and edgedeletion NPcomplete problems Proceedings of the tenth anual ACM Symposium on Theory of Computing (STOC'78) 253264 (1978) 
1631 
M. Yannakakis Node and edgedeletion NPcomplete problems Proceedings of the tenth anual ACM Symposium on Theory of Computing (STOC'78) 253264 (1978) 
1632 
J. Blazewicz, M. Kasprzak, B. LeroyBeaulieu, D. de Werra Finding Hamiltonian circuits in quasiadjoint graphs Discrete Appl. Math. 156 25732580 (2008) doi 10.1016/j.dam.2008.03.014 
1633 
J. Blazewicz, M. Kasprzak Reducedbymatching graphs: toward simplifying Hamiltonian circuit problem Fundamenta Informatica 118 225244 (2012) 
1634 
N. Apollonio, P.G. Franciosa A characterization of partial directed line graphs Discrete Math. 307 2598 2614 (2007) 
1635 
D. Lokshantov, M. Vatshelle, Y. Villanger Independent set in P5free graphs in polynomial time Accepted for publication 
1636 
S. Chaplick, T. Ueckerdt Planar graphs as VPGGraphs Journal of Graph Algorithms and Applications Vol.17 No.4 475294 (2013) doi 10.7155/jgaa.00300 JGAA 
1637 
O. Daescu, A. Kurdia Towards an optimal algorithm for recognizing Laman graphs Journal of Graph Algorithms and Applications Vol.13 No.2 219232 (2009) doi 10.7155/jgaa.00185 JGAA 
1638 
S. Kobourov, T. Ueckerdt, K. Verbeek Combinatorial and geometric properties of planar Laman graphs Proc. of the 24th annual ACMSIAM symposium on Discrete algorithms SODA 2013 16681678 (2013) 
1639 
S. Chaplick, V. Jelinek, J. Kratochvil, T. Vyskocil Bendbounded path intersection graphs: Sausages, noodles and waffles on a grill Proceedings of WG 2012, Lecture Notes in Computer Science 7551, 274285 (2012) 
1640  By a wellknown result of Bollobas and Thomason the number of (4,0)colorable graphs on n vertices is $2^{\frac{3}{4}\binom{n}{2} + o(n^2)}$. However, it is known that the number of planar graphs on n vertices (and hence the number of coplanar graphs on n vertices) is approximately $c^n n! = 2^{o(n^2)}$ (for a sharp result, see Giménez and Noy). Hence, almost every (4,0)colorable graph is not coplanar. (Communicated by Andrew Uzzell) 
1641 
Graphclass: tree. Problem: Clique cover. Tree has no cycles, so each clique is either a single vertex or an edge with both ends. So the Clique cover problem is equivalent to Maximum matching problem (i.e. for any tree T the minimum clique cover size in the sum with maximum matching size is equal to the order of T), which can be solved in linear time using following dynamic programming. Let's consider tree as rooted tree and for each vertex v we denote A(v) the maximum size of matching in subtree of v with some edge adjacent to v and B(v) the maximum size of matching in subtree of v with no edge adjacent to v. Then B(v) = sum (over all sons u of vertex v) max { A(u), B(u) } and A(v) = max (over all sons u of vertex v) B(v)  max { A(u), B(u) } + B(u). Then max{A(r), B(r)}, where r is the root, is the size of maximum matching in the whole tree. (Communicated by Pavel Irzhavski) 
1642  By definition, a graph G is maximal clique irreducible if every maximal clique in G contains an edge that is not contained in any other maximal clique. Then, the number of maximal cliques is bounded by m, the number of edges. Thus, the maximal cliques can be obtained in polynomial time (with any algorithm that lists the cliques one by one). This solves the clique and weight clique problems. For the recognition problem, observe that you can return NO if more than m maximal cliques are found by the enumeration algorithm. Otherwise, we just check that every maximal clique has an edge not contained in other maximal cliques. 
1643 
M.C. Lin, F. Soulignac, J.L. Szwarcfiter Arboricity, hindex and dynamic algorithms Theoret. Comput. Sci. 426 7590 (2012) doi 10.1016/j.tcs.2011.12.006 
1644 
J.P. Spinrad Recognizing quasitriangulated graphs Discrete Appl. Math. 138 No.12 203213 (2004) doi 10.1016/S0166218X(03)002956 
1645 
M.R. Eguia, F.J. Soulignac Hereditary bicliqueHelly graphs: recognition and maximal biclique enumeration DMTCS 15 No.1 (2013) Available here. 
1646 
M.C. Lin, F. Soulignac, J.L. Szwarcfiter A simple linear time algorithm for the isomorphism problem on proper circulararc graphs LNCS 5124 355366 (2008) doi 10.1007/9783540699033_32 
1647 
L.N. Grippo, M.D. Safe On circulararc graphs having a model with no three arcs covering the circle Anais do XLIV Simpósio Brasileiro de Pesquisa Operacional, 40934104 (2012) Available here. 
1648 
On 2subdivision graphs we have the following algorithms and reductions:

1649 
D.P. Dailey Uniqueness of colorability and colorability of planar 4regular graphs are NPcomplete Discrete Math. 30 No.3 289293 (1980) 
1650 
L. Stockmeyer Planar 3colorability is polynomial complete SIGACT News 1925 (1973) 
1651 
F.J. Soulignac On proper and Helly circulararc graphs Ph.D. Thesis Universidad de Buenos Aires (2010) 
1652  Let $u,v,w$ be the vertices of a triangle to start the construction of a 3tree. Attach a vertex y1 to ${u,v,w}$ and y2 to ${u,v,w}$ and y3 to ${u,v,w}$. These are valid 3tree construction steps and results in a 3tree with a K_{3,3} partial subgraph, which is not planar. It follows that planar partial 3trees are a proper subclass of partial 3trees. (Communicated by G. Borradaile) 
1653 
C.H. Papadimitriou, U.V. Vazirani On two geometric problems related to the travelling salesman problem J. of Algorithms 5 No.2 231246 (1984) 
1654 
A.E. Feldmann, P. Widmayer An O(n^4) time Algorithm to Compute the Bisection Width of Solid Grid Graphs Proc. of the 19th Annual European Symposium on Algorithms (ESA) (2011) 
1655 
On star convex graphs we have the following algorithms and reductions:

1656 
It is easy to see that $H_{n,q}$ graph doesn't have Hamiltonian path (and therefore cycle) for $n \ge 3$ since in case of existance of Hamiltonian path the outer cycle with exception of at most one edge should be part of this path because of vertices of degree 2. But there are at least 4 inner vertices that should be ends of path or be adjacent in Hamiltonian path with vertices of outer cycle. In case n = 2 graph is a simple cycle and in case n = 1 graph has only one vertex. Both cases are trivial, so the problems are linear time solvable. Recognition is also linear. Cases of n = 1 (single vertex) and n = 2 (simple cycle of length 12q) are trivial, so let n be at least 3. It is easy to see that graph $H_{n,q}$ has 6qn(n1) edges. Consider maximal paths with nonend vertices of degree 2. All of them can be found using one DFS. The longest such path has 6q edges. So now both n and q are known (since equation n(n1) = a has at most one positive integer root). Now we can try to extract all vertices of $H_{n,q}$ from the given graph, moving diagonal wave from one corner to the other. For the $F_n$ grids similar arguments apply. (P. Irzhavsky) 
1657 
J. Hopcroft, R. Tarjan Efficient algorithms for graph manipulation C.ACM 16 No.6 372378 (1973) 
1658 
W.k. Shih, S. Wu, Y.S. Kuo Unifying Maximum Cut and Minimum Cut of a Planar Graph IEEE Transactions on Computer 39 No.5 694697 (1990) 
1659 
If, in the notation of
[1327]
, the intersection
graph H of (C,coA) is not chordal, then there are three arcs coA_1,
coA_2 and coA_3 in coA corresponding to three consecutive vertices of
some chordless cycle of length at least 4 in H and, consequently, A_1,
A_2 and A_3 together cover the circle. Therefore, a model not having
three arcs covering the circle satisfies (i) and (ii) of Theorem 1 of
Min Chih Lin, Jayme Luiz Szwarcfiter
Characterizations and linear time recognition of Helly circulararc graphs Proceedings of the twelfth Annual International Conference on Computing and Combinatorics (COCOON'06), Lecture Notes in Computer Science 4112, 7382 (2006)
[1327]
and, hence, it is Helly. To see that it is also
normal (i.e., has no two arcs covering the circle) is much eaiser: if one
is forced to cover the circle with two arcs, then the graph has at least
three vertices and so in any model of such a graph if there were two arcs
covering the circle then there would be also three arcs covering the
circle.
Min Chih Lin, Jayme Luiz Szwarcfiter
Characterizations and linear time recognition of Helly circulararc graphs Proceedings of the twelfth Annual International Conference on Computing and Combinatorics (COCOON'06), Lecture Notes in Computer Science 4112, 7382 (2006) Similar reasoning applies to proper Helly circulararc and unit Helly circular arc graphs. (M.D. Safe) 
1660  Consider an arbitrary 2connected, cubic, planar graph $G$ and an edge $uv$ of $G$. At first let's replace edge $uv$ by vertices $a, b, x, y$ and edges $\{u, a\}, \{a, x\}, \{a, y\}, \{x, b\}, \{y, b\}, \{b, v\}$. Replace $x$ and $y$ by diamond s $X$ and $Y$, respectively: $x$ is replaced by $x_1, x_2, x_3, x_4$, edges $\{a, x\}, \{x, b\}$ are replaced by $\{a, x_1\}, \{x_2, b\}$ and the edges $\{x_1, x_3\}, \{x_1, x_4\}, \{x_3, x_4\}, \{x_3, x_2\}, \{x_4, x_2\}$ are added. And the same for $y$. Now any Hamiltonian path in the resulting graph $H$ starts with either the vertices of $X$ or the vertices of $Y$. Without loss of generality, assume it starts with the vertices of $X$. The path is of one of the forms $X,a,Y,b,v,\dots,u$; or $X,b,Y,a,u,\dots,v$; or $X,b,v,\dots,u,a,Y$; or $X,a,u,\dots,v,b,Y$. Hence a Hamiltonian path in $H$ exists iff $G$ has a Hamiltonian cycle with edge $uv$. (P. Irzhavsky) 
1661 
M. Conforti, G. Cornuejols, K. Vuskovic Decomposition of oddholefree graphs by double star cutsets and 2joins Discrete Appl. Math. 141 No.13 4191 (2004) 
1662 
M.V.G. da Silva, K. Vuskovic Decomposition of evenholefree graphs with star cutsets and 2joins J. of Combin. Th. (B) 103 No.1 144183 (2013) 
1663 
M. Kaminski, V. Lozin Vertex 3colorability of clawfree graphs Algorithmic Operations Research Vol.2 1521 (2007) 
1664 
J. Mycielski Sur le coloriage des graphes Colloq. Math. 3 161162 
1665 
V. Lozin, M. Milanic On the Maximum Independent Set Problem in Subclasses of Planar Graphs Journal of Graph Algorithms and Applications Vol.14 No.2 269286 (2010) doi 10.7155/jgaa.00207 JGAA 
1666 
I.E. Zverovich, O.I. Zverovich Independent Domination in hereditary classes Theoretical Comp. Sci. 352 215225 (2006) doi 10.1016/j.tcs.2005.10.049 
1667 
P. Zhang A study on generalized solution concept in constraint satisfaction and group colouring M.Sc. Thesis, University of British Columbia (2014) If $G$ and $G'$ have the same P_{4} structure, then $G$ is $P_4$bipartite iff $G'$ is. Hence, if $C$ is a subclass of $P_4$bipartite, then so is the class $C$perfect. (Communicated by J. Nastos) 
1668 
I.E. Zverovich Satgraphs and independent Domination. Part 1 Theoretical Comp. Sci. 352 4756 (2006) doi 10.1016/j.tcs.2005.08.038 
1669 
M. Farber Independent domination in chordal graphs Operations Research Lett. 1 No.4 134138 (1982) doi 10.1016/01676377(82)900153 
1670 
A. Gyarfas Generalized split graphs and Ramsey numbers J. of Combin. Th. (A) 81 255261 (1998) 
1671 
D.V. Andrade, L.H. de Figueiredo Good Approximations for the Relative Neighbourhood Graph Proc. of the 13th Canadian Conference on Computation Geometry CCCG'01 2528 (2001) 
1672 
J.W. Jaromczyk, G.T. Toussaint Relative Neighborhood Graphs and Their Relatives Proc. of the IEEE 80 No.9 15021517 (1992) 
1673 
A. Lubiw Visibility graphs, dismantlability and the copsandrobbers game Workshop on Graphs and Algorithms, Fields Institute, May 56 (2014) 
1674 
H.C. Chang, H.I. Lu A faster algorithm to recognize evenholefree graphs Proceedings of the 23rd Annual ACMSIAM Symposium on Discrete Algorithms (SODA'12), 12861297, (2012) 
1675  Proof on stackexchange (M. De Biasi) 
1676 
M. Kaminski Maxcut and containment relations in graphs Proceedings of WG 2010, Lecture Notes in Computer Science 6410, 1526 (2010) 
1677 
F. Barahona The maxcut problem on graphs not contractible to $K_5$ Oper. Res. Lett. 2 No.3 107111 (1983) 
1678 
V. Guruswami Maximum cut on line and total graphs Discrete Appl. Math. 92 217221 (1999) doi 10.1016/S0166218X(99)000566 
1679 
M.S. Chang, L.J. Hung Recognition of probe ptolemaic graphs Proceedings of IWOCA 2010 LNCS 6460 286290 (2011) 
1680 
Y. Nussbaum Recognition of probe proper interval graphs Discrete Appl. Math. 167 228238 (2014) 
1681 
M.S. Chang, L.J. Hung, P. Rosssmanith Recognition of probe distancehereditary graphs Discrete Appl. Math. 161 336348 (2013) 
1682 
G. Di Stefano Distancehereditary comparability graphs Discrete Appl. Math. 160 26692680 (2012) 
1683 
C.M. Lee, M.S. Chang Distancehereditary graphs are cliqueperfect Discrete Appl. Math. 154 525536 (2006) 
1684 
J. Hopcroft, J. Wong Linear time algorithm for the isomorphism of planar graphs Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, 172184 (1974) doi 10.1145/800119.803896 
1685 
H. Bodlaender Polynomial algorithms for graph isomorphism and chromatic index on partial ktrees J. Algorithms 11 No.4 631643 (1990) doi 10.1016/01966774(90)900135 
1686 
I.S. Filotti, J.N. Mayer A Polynomialtime Algorithm for Determining the Isomorphism of Graphs of Fixed Genus Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing STOC'80 236243 (1980) doi 10.1145/800141.804671 
1687 
G. Miller Isomorphism testing for graphs of bounded genus Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing STOC'80 225235 (1980) doi 10.1145/800141.804670 
1688 
V.N. Zemlyachenko, N.M. Korneenko, R.I. Tyshkevich Graph isomorphism problem J. of Soviet Mathematics 29 No.4 14261481 doi 10.1007/BF02104746 
1689 
R. Uehara, S. Toda, T. Nagoya Graph isomorphism completenes for chordal bipartite graphs and strongly chordal graphs Discrete Appl. Math. 145 No.3 479482 doi 10.1016/j.dam.2004.06.008 
1690 
S. Kratsch, P. Schweitzer Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs Proceedings of WG 2012, Lecture Notes in Computer Science 7551, 3445 (2012) 
1691 
E.M. Luks Isomorphism of graphs of bounded valence can be tested in polynomial time Journal of Computer and System Sciences 25 4265 (1982) doi 10.1016/00220000(82)900095 
1692 
H.J. Broersma, H.J. Veldman Restrictions on induced subgraphs ensuring Hamiltonicity or pancyclicity of $K_{1,3}$free graphs Contemporary methods in graph theory, BIWiss.Verl. 181194 (199) 
1693 
R. Faudree, E. Flandrin, Z. Ryjacek Clawfree graphs  a survey Discrete Math. 164 87147 (1997) doi 10.1016/S0012365X(96)000453 
1694  Since every 2connected (P_{6} ,claw )free graph is hamiltonian and every hamiltonian graph is 2connected, it is straightforward to check whether a (P_{6} ,claw )free graph has a Hamiltonian cycle. (Communicated by S.i. Oum) 
1695 
F.R.K. Chung On the cutwidth and the topological bandwidth of a tree SIAM J. Alg. Discr. Meth. 6 1985 268277 
1696 
F.R.K. Chung, P.D. Seymour Graphs with small bandwidth and cutwidth Disc. Math. 75 1989 113119 
1697 
E. DeLaVina, B. Waller A NOTE ON A CONJECTURE OF HANSEN ET AL. manuscript 2009 http://cms.dt.uh.edu/faculty/delavinae/research/DelavinaWaller2009.pdf 
1698 
D.J. Kleitman, D.B. West Spanning trees with many leaves SIAM J. Alg. Discr. Meth. 4 1991 99106 
1699 
R. Sasák Comparing 17 graph parameters Master's thesis, University of Bergen 2010 