How to plot planar graphs as such?

You can plot it using the GraphLayout option, which has, since v9, "PlanarEmbedding" as a possible value:

Graph[Rule @@@ {{1, 2}, {2, 3}, {3, 1}, {1, 4}, {3, 4}, {2, 4}}, GraphLayout -> "PlanarEmbedding"]

Mathematica graphics.

(BTW: This is the standard Mathematica Graph, not the Combinatorica Graph function)

Another one:

truncatedCube =
  {{0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1}, 
   {1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1}, {1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0}, 
   {0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0}, {1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0}, 
   {0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, 
   {0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
   {0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, {1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, 
   {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};

AdjacencyGraph[truncatedCube, 
  GraphLayout -> "PlanarEmbedding", 
  VertexLabels -> Array[# -> # &, Length @ truncatedCube], 
  PlotRangePadding -> 0.5]

Mathematica graphics

Without GraphLayout -> "PlanarEmbedding":

Mathematica graphics


I wouldn't know how to do this automatically but you could untangle the graphs manually using Manipulate:

untangle[gr_] :=
 DynamicModule[{edges, vv, plrnge, gap},
  gap = .15;
  edges = EdgeList[gr];
  vv = VertexList[gr];
  plrnge = 
   Through[{Min, Max}[#]] & /@ 
    Transpose[
     OptionValue[AbsoluteOptions[gr, VertexCoordinates], 
      VertexCoordinates]];
  Manipulate[
   pt = Round[pt, .15];
   Graph[vv, edges, VertexCoordinates -> pt,
    EdgeStyle -> {{Darker[Gray], Thickness[Large]}},
    VertexSize -> 0,
    GridLines -> (Range[Floor[#1 - 1, gap], #2 + 1, gap] & @@@ plrnge),
    GridLinesStyle -> Opacity[.3],
    PlotRange -> plrnge + {{-1, 1}, {-1, 1}},
    Epilog -> {EdgeForm[Black], FaceForm[Red], 
      Disk[#, .03] & /@ pt}],
   {{pt, OptionValue[AbsoluteOptions[gr, VertexCoordinates],
      VertexCoordinates]}, Locator, Appearance -> None},
   Button["Paste graph", Print[Graph[vv, edges, VertexCoordinates -> pt]]]]]

Example

For some arbitrary test graph this looks like

<< ComputationalGeometry`
graph = Graph@
   Union[Sort /@ 
     Join @@ (Thread /@ DelaunayTriangulation@RandomReal[1, {20, 2}])];
untangle[graph]

Before:

Mathematica graphics

And after manually untangling the vertices:

Mathematica graphics

The pasted untangled graph looks like:

Mathematica graphics


There are the built-in "PlanarEmbedding" and "TutteEmbedding" GraphLayouts.

IGraph/M brings additional planar graph visualization functions, IGLayoutPlanar and IGLayoutTutte. IGLayoutPlanar implements a different algorithm than "PlanarEmbedding" and IGLayoutTutte allows specifying the outer face, and considers edge weights (the builtin one can do neither). In addition to IGraph/M's documentation, there are some demos in this post.